# Number Theory

The question is

Use Fermat's Theorem to compute the following:

$$99^{99} \equiv (mod 47)$$

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

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

Thanks

Related Introductory Physics Homework Help News on Phys.org
lurflurf
Homework Helper
pivoxa15 said:
The question is

Use Fermat's Theorem to compute the following:

$$99^{99} \equiv (mod 47)$$

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

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.

lurflurf
Homework Helper
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.

lurflurf, yes I meant Fermat's little theorem but how would you do 99^4 (mod 47) quickly?

Thanks

lurflurf
Homework Helper
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

matt grime