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 a711(mod7).



331(mod7)3636363637(mod7)111133(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 3333401(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




329(mod23)
348112(mod23)
381446(mod23)
3163613(mod23)
3173916(mod23)



See Exponentiation by squaring and Modular exponentiation on Wikipedia.


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...