# 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 $\displaystyle a_{n + 1} \equiv {a_n}^3 \pmod{113}$, $\displaystyle a_1$ being the initial term.

If I tell you that $\displaystyle a_4 = 26$, can you find $\displaystyle 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 $\displaystyle a_1^{112} = 1 \mod 113$
Following the recursion gives $\displaystyle a_1^{27} = 26 \mod 113$. But $\displaystyle a_1^{27} = 26 \mod 113 \implies a_1^{108} = 26^4 \mod 113 \implies a_1^{4} = 26^{-4} \mod 113$
So definitely $\displaystyle a_1 = 13 \mod 113$ is one possible answer. I dont know whether there are more.
• Dec 29th 2009, 12:46 PM
Bacterius
Hello,

$\displaystyle a_1 = 13$

$\displaystyle a_2 = 50$

$\displaystyle a_3 = 22$

$\displaystyle 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)