# Number Theory

I have got another question, this time involving the Euler's Theorem:

a^(phi(m)) is congruent to 1 (mod m)

The question is calculate

7^40002 mod 1000

I could only reduce it to

7^402 mod 1000

What should I do now?

Thanks

lurflurf
Homework Helper
pivoxa15 said:
I have got another question, this time involving the Euler's Theorem:

a^(phi(m)) is congruent to 1 (mod m)

The question is calculate

7^40002 mod 1000

I could only reduce it to

7^402 mod 1000

What should I do now?

Thanks
Again with the vague theorem referrence. This time you clearly mean Eulers Totient Theorem. Why not reduce once more?
we have 7 relatively prime to 1000.
phi(1000)=1000-1000/2-1000/5+1000/10=1100-700=400
so (all mod 1000)
7^400=1
7^40002=((7^400)^100)(7^2)=(1^100)(7^2)=7^2=49

Thanks lurlurf, I didn't apply the Euler Totient theorem fully but I have another one

11^100 (mod 72)

This time I reduced it to 11^4 (mod 72)

I could evaluate it by hand which works out to be 7^4 (mod 72) but is there a better way of doing it.

Thanks

matt grime
Homework Helper
11^4 is 121^2 and you can reduce 121 can't you? so 99^2 then, which is (40+9)^2 whcih is quite easy to work out and reduce esp since 72 divides 1440, hence 1512 and thus 1584 so it's what?

6+2.40.9+81=6+9=15

Gokul43201
Staff Emeritus
Gold Member
Wait a minute :

11^4 = 121^2 == (-23)^2 = 529 =(72*7) + 25

So, 11^4 == 25 (mod 72)....no?

matt grime