I'm new to Fermat's theorem (a, and I am familiar with how to use it in basic cases with relatively large numers (i.e. 2^345 mod 31). I was given the question to find 4^(2^2006), and found myself stuck with wrong answers (when comparing to the result on WolfRamAlpha of 8. How would I perform a calculation in the form of x^y^z mod m using Fermat's little theorem? Anything helps. Cheers!
Edit: What I have tried was as follows:
422006 --> exponent: 22006
exponent's exponent: 2006
Since I want mod 31, I attempted 2006 mod 31 = 22, then one level down...
222 mod 31 = 4, then again, the last level down...
44 = 256 mod 31 = 8.
While 8 is the correct answer, I do not believe this is the correct method to get the solution.
i suck at latex sry if someone could format this for me that would be great i believe this is a sol. not using f.l.t. as far as i can tell... i wonder if there is a faster way of doing it? it was like i just looked for the 1st power of 4 that =1 then divided out that power over and over till it 0ed out. what what was left was the answer.
4^15 mod 31 =1 4^(2^4) (mod 31)≡ 4^16 mod 31
≡4^15 * 4 mod 31
≡ (4^15 mod 31 * 4 mod 31)
≡ (1 * 4 mod 31) = 4
4^(2^2006 ) (mod 31)≡ 4^(2^2004* 2^2 ) (mod 31)
≡(4^(2^4 ))^(2^2000*2^2 ) (mod 31)
≡ 4^(16)^(2^2000 2^2 ) (mod 31)
≡ (4^15 * 4 )^(2^2000* 2^2 ) mod 31 ≡ (4^15 (mod 31) * 4 (mod 31) )^(2^2000* 2^2 )
≡ (1 * 4 (mod 31) )^(2^2000* 2^2 )
≡ 4^(2^2000* 2^2 ) mod 31
≡4^(2^4 *2^1998 ) (mod 31) ) ≡(4^15 * 4 (mod 31) )^(2^1998 ) ≡(4^(2^1998 ))(mod 31)
≡4^(2^4 *2^1994) (mod 31) ) ≡(4^15 * 4^1 (mod 31) )^(2^1994 )
≡4^(2^1994 )(mod 31)≡ 4^((2^1992)*2^2)
Continue in this way . . . ≡ 4^(2^0*2^2) ≡(4^(2^2 )) (mod 31) ≡(4^4) (mod 31) ≡8 Hence 4^(2^2006 ) (mod 31)≡8