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

Number Theory

  • Thread starter pivoxa15
  • Start date
  • #1
2,255
1
The question is

Use Fermat's Theorem to compute the following:

[tex]99^{99} \equiv (mod 47)[/tex]

I spent over an hour on it but could only reduce it to [tex]99^7 \equiv (mod 47) [/tex]

I think I am missing something. So if you can help, it would be great. Please provide an explanation as well.

Thanks
 

Answers and Replies

  • #2
lurflurf
Homework Helper
2,432
132
pivoxa15 said:
The question is

Use Fermat's Theorem to compute the following:

[tex]99^{99} \equiv (mod 47)[/tex]

I spent over an hour on it but could only reduce it to [tex]99^7 \equiv (mod 47) [/tex]

I think I am missing something. So if you can help, it would be great. Please provide an explanation as well.
You are missing something
99=64+32+2+1
find
99^1 (mod 47)
99^2 (mod 47)
99^4 (mod 47)
99^8 (mod 47)
99^16 (mod 47)
99^32 (mod 47)
99^64 (mod 47)
by repeated squaring
then find
(99^64)(99^32)(99^2)(99^1) (mod 47)
recall that at each step you may reduce mod 47 so in no step do you need to compute with a number larger than 46.
 
  • #3
lurflurf
Homework Helper
2,432
132
I now see the part about Fermats Theorem. Fermat had many theorems, I assume you mean Fermats little theorem.
So by Fermats little theorem
99^47=99 (mod 47)
99^99=(99^47)^2(99^5)=99^7 (mod 47) then the method I listed abouve can be used, but now less squares are needed
7=1+2+4
find
99^1 (mod 47)
99^2 (mod 47)
99^4 (mod 47)
then multiply them and reduce modulo 47
again making reductions modulo 47 as needed.
 
  • #4
2,255
1
lurflurf, yes I meant Fermat's little theorem but how would you do 99^4 (mod 47) quickly?

Thanks
 
  • #5
lurflurf
Homework Helper
2,432
132
pivoxa15 said:
lurflurf, yes I meant Fermat's little theorem but how would you do 99^4 (mod 47) quickly?

Thanks
By repeated squaring with reduction modulo 47 as needed.
all bellow is mod 47
99^1=2*47+5=5
99^2=5^2=25
99^4=25^2=625=13*47+14=14
or even easier
99^4=5^3*5=125*5=(2*47+31)*5=31*5=155=14+3*47=14
 
  • #6
matt grime
Science Advisor
Homework Helper
9,395
3
remember that in mod arithmetic you cah reduce any numver mod whatever anytime you need to. 99=5 mod 47, that should be your first step.
 

Related Threads on Number Theory

  • Last Post
Replies
5
Views
6K
  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
2
Views
891
  • Last Post
Replies
3
Views
870
  • Last Post
Replies
1
Views
705
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
2
Views
1K
Replies
0
Views
2K
  • Last Post
Replies
6
Views
888
Top