Number Theory

  • Thread starter pivoxa15
  • Start date
  • #1
2,259
1
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
 

Answers and Replies

  • #2
lurflurf
Homework Helper
2,440
138
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
 
  • #3
2,259
1
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
 
  • #4
matt grime
Science Advisor
Homework Helper
9,420
4
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
 
  • #5
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
7,082
20
Wait a minute :

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

So, 11^4 == 25 (mod 72)....no?
 
  • #6
matt grime
Science Advisor
Homework Helper
9,420
4
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.
 

Related Threads on Number Theory

  • Last Post
Replies
2
Views
981
  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
3
Views
946
  • Last Post
Replies
1
Views
813
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
2
Views
2K
Replies
0
Views
2K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
3
Views
652
Top