# Last 2 digits of 3^400

• Oct 2nd 2009, 02:06 PM
ilikecandy
Last 2 digits of 3^400
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?
• Oct 2nd 2009, 02:37 PM
skyskiers
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?
• Oct 2nd 2009, 02:43 PM
ilikecandy
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 (Clapping). By the way, how do you calculate phi(m) in general?
• Oct 2nd 2009, 03:39 PM
Matt Westwood
Quote:

Originally Posted by ilikecandy
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 (Clapping). 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