• Support PF! Buy your school textbooks, materials and every day products Here!

Number Theory

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

lurflurf
Homework Helper
2,419
122
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
 
2,234
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
 
matt grime
Science Advisor
Homework Helper
9,394
3
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
Science Advisor
Gold Member
6,987
14
Wait a minute :

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

So, 11^4 == 25 (mod 72)....no?
 
matt grime
Science Advisor
Homework Helper
9,394
3
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 for: Number Theory

  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
2
Views
870
  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
3
Views
848
  • Last Post
Replies
1
Views
686
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
2
Views
1K
Replies
0
Views
2K
Top