Why: to make modulo and power calculations easier !
I will take an example to show my thoughts on Fermats Little theorem , Assume we want to calculate 331(mod7)
We see that 7 is prime therefore i directly know that 37≡3(mod7) and a7−1≡1(mod7).
331(mod7)≡36∗36∗36∗36∗37(mod7)≡1∗1∗1∗1∗3≡3(mod7)
I will take another example to show my thoughts on Euler's theorem , Assume we want to calculate 33334444(mod100)
We see that 100 is not a prime number, therefore we can use Euler's theorem !
We start by checking GCD(3333,100) which is 1 therefore 3333φ(100)≡1(mod100)
We calculate φ(10)=4 therefore we get 333340≡1(mod100)
And then we continue simplifying..
As i know, Euler's theorem is a generalization of fermats little theorem. so can can we use Euler's theorem instead of fermat little therom, when trying to calculate ax(modm) where m is a prime number?
A side question:
how would you calculate 340(mod23)?
i tried with FLT and got stuck at 317(mod23), is it possible to simplify it a bit more ?
Answer
For 317(mod23), you could do
32≡9(mod23)
34≡81≡12(mod23)
38≡144≡6(mod23)
316≡36≡13(mod23)
317≡39≡16(mod23)
See Exponentiation by squaring and Modular exponentiation on Wikipedia.
No comments:
Post a Comment