Monday, 3 June 2019

elementary number theory - Find $11^{644} mod 645$




Can someone just explain to me the basic process of what is going on here? I understand everything until we start adding 1's then after that it all goes to hell. I just need some guidance. The Problem with the solution is attached.




Thanks in advance..



Find $11^{644} \mod 645$



enter image description here


Answer



Note that $645=3\cdot 5\cdot 43$. Then



$$11^{644}\equiv (-1)^{2\cdot 322}\equiv 1^{322}\equiv 1\pmod 3$$
$$11^{644}\equiv 1^{644}\equiv 1\pmod 5$$

For the last modulus, we should determine the order of $11\pmod{43}$. To this end we first try $11^q$ for $q\mid p-1$:
$$11^2\equiv 35\equiv -8, 11^3\equiv -8\cdot 11\equiv -2, 11^7\equiv (-8)^2\cdot(-2)\equiv -128\equiv 1.$$
So with this
$$11^{644}\equiv 11^{7\cdot 46}\equiv 1^{46}\equiv 1\pmod{43} $$
and so by the Chinese Remainder Theorem also $11^{644}\equiv 1\pmod {645}$


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}...