Tuesday, 12 April 2016

number theory - Have i understood Fermat little theorem and Euler's theorem correctly?



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 373(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

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...