Number theory challenge

Printable View

December 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 ...
December 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.
December 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)

All times are GMT -8. The time now is 03:52 AM.

Copyright © 2005-2013 Math Help Forum. All rights reserved.

Copyright © 2005-2013 Math Help Forum. All rights reserved.