Sunday, 2 October 2016

elementary number theory - Find 61000mod23





Find 6^{1000} \mod 23




Having just studied Fermat's theorem I've applied 6^{22}\equiv 1 \mod 23 , but now I am quite clueless on the best way to proceed.



This is what I've tried:



Raising everything to the 4th power I have 6^{88} \equiv 1 \mod 23 6^{100} \equiv 6^{12} \mod 23 6^{1000}\equiv 6^{120} \mod 23 6^{1000} \equiv 6^{10} \mod 23 How do I simplify now the right hand side of the congruence ?



Answer



We may exploit the fact that 1000\equiv 10\pmod{22} to get:
6^{1000}\equiv 6^{10} \equiv (6^5)^2 \equiv 2^2 \equiv\color{red}{4}\pmod{23}.
As an alternative, we may notice that a^{11}\pmod{23} is the Legendre symbol \left(\frac{a}{23}\right), so:



6^{11} \equiv \left(\frac{2}{23}\right)\cdot\left(\frac{3}{23}\right) \equiv 1\cdot 1\equiv 1\pmod{23}
gives 6^{1001}\equiv 1\pmod{23} and by multiplying both sides by the inverse of 6 we get 4 as above.


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