# Number theory challenge

• Dec 29th 2009, 02:11 AM
Bacterius
Number theory challenge
Hi all, here is a little challenge for you all, involving number theory.

Quote:

Let $a_{n + 1} \equiv {a_n}^3 \pmod{113}$, $a_1$ being the initial term.

If I tell you that $a_4 = 26$, can you find $a_1$ ?
Good luck :)

Please don't just try all possible values ...
• Dec 29th 2009, 04:23 AM
Isomorphism
Quote:

Originally Posted by Bacterius
Hi all, here is a little challenge for you all, involving number theory.

Good luck :)

Please don't just try all possible values ...

From Fermat's Little theorem, we have $a_1^{112} = 1 \mod 113$
Following the recursion gives $a_1^{27} = 26 \mod 113$. But $a_1^{27} = 26 \mod 113 \implies a_1^{108} = 26^4 \mod 113 \implies a_1^{4} = 26^{-4} \mod 113$
So definitely $a_1 = 13 \mod 113$ is one possible answer. I dont know whether there are more.
• Dec 29th 2009, 12:46 PM
Bacterius
Hello,

$a_1 = 13$

$a_2 = 50$

$a_3 = 22$

$a_4 = 26$

That was exactly the one I was thinking of :) Would you have taken the same time if I had taken a five-digit modulus ?

Well done anyway (Clapping)