Solve 99^99 congruent to (mod 47) using Fermat's Theorem

[pivoxa15]

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

 

[lurflurf]

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]

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.

 

[pivoxa15]

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

Thanks

 

[lurflurf]

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]

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.