Hello,
Am not sure why you want to reach to 3^20
Its quite straight forward using eulers theorem
3 and 100 are coprime.
So phi[100] = 100 [1/2][4/5] = 40
So, (3^40) = 1 mod 100
=> 3^400 =1 mod 100
So remainder is 01
Does that make sense?
Hello. I want to find the last 2 digits of 3^400 using modular arithmetic. What I have so far...
3^20 congruent to 1 (mod 25) using Euler's theorem.
3^2 congruent to 1 (mod 4) using Euler's theorem again.
I want to somehow reach 3^20 congruent to 1 (mod 100), and from there show that the last two digits are 01, but I have no clue. Can anyone help?
Thanks! My textbook has hints at the back of the book, which says that I should establish that 3^20=1(mod 25), and that 3^2=1(mod4), and that finally, 3^20=1mod(100). Your solution makes much more sense . By the way, how do you calculate phi(m) in general?
here's a link that may help:
Euler Phi Function of an Integer - ProofWiki