Calculating 7^402 mod 1000 with Euler's Theorem

[pivoxa15]

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]

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

 

[pivoxa15]

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]

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]

Wait a minute :

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

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

 

[matt grime]

oh i don't claim to have got the arithmetic right, only the method. i am a mathematician after all. i know how to solve it, doesn't mean i can get it rgight when i try.