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 a^{7-1} \equiv 1 \pmod 7.
3^{31} \pmod7 \equiv 3^{6}*3^{6}*3^{6}*3^{6}*3^{7} \pmod7 \equiv 1*1*1*1*3 \equiv 3 \pmod7
I will take another example to show my thoughts on Euler's theorem , Assume we want to calculate 3333^{4444}( mod 100)
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^{\varphi(100)}\equiv 1 (mod 100)
We calculate \varphi(10) = 4 therefore we get 3333^{40} \equiv 1 (mod 100)
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 a^x \pmod m where m is a prime number?
A side question:
how would you calculate 3^{40} (mod 23) ?
i tried with FLT and got stuck at 3^{17} (mod 23), is it possible to simplify it a bit more ?
Answer
For 3^{17} \pmod{23}, you could do
3^2\equiv9\pmod{23}
3^4\equiv81\equiv12\pmod{23}
3^8\equiv144\equiv6\pmod{23}
3^{16}\equiv36\equiv13\pmod{23}
3^{17}\equiv39\equiv16\pmod{23}
See Exponentiation by squaring and Modular exponentiation on Wikipedia.
No comments:
Post a Comment