Show that $2^{341}\equiv2\pmod{341}$
Mia Lopez 
Show that $2^{341}\equiv2\pmod{341}$
My work:
Prime factorization of $341 = 31\cdot11$, thus $2^{11\cdot31}\equiv2\pmod{31\cdot11}$
$2^{341} = 2=2(2^{340}-1)$, we have $2^{340}\equiv1\pmod{341}$
$2^{340}=4^{175}=1024^{35}$
$1024\equiv1\pmod{341}$
$1024^{35}\equiv1^{35}\pmod{341}$
$(4^5)^{35}\equiv1\pmod{341}$
$2^{340}\equiv1\pmod{341}$
Am I right??
And someone please teach me how to use Fermat little theorem to prove this problem, please...
$\endgroup$ 3
2 Answers
$\begingroup$Yes, $\rm\: mod\ 341\!:\ (2^{10})^{34}\!\equiv 1024^{34}\equiv(1+3\cdot 341)^{34}\!\equiv 1^{34}\!\equiv 1,\ $ so $\rm\ 2^{340}\!\equiv 1\:\Rightarrow\:2^{341}\!\equiv 2\cdot 1$
Remark $\ $ Or you could note $\rm\: 2^5\! =32 \equiv \pm1\,\ (mod\ 31,11)\:\Rightarrow\ 2^{10}\!\equiv 1\ (mod\ 31\cdot 11)$
More generally $\rm\ b\mid a^k\!-1,\ c\mid a^k\!+1\:\Rightarrow\:bc\mid a^{2k}\!-1\mid a^{2kn}\!-1$
said modularly $\ \ \begin{eqnarray}\rm a^k&\equiv&\rm \ \ \ 1\,\ (mod\ b)\\ \rm a^k&\equiv&\rm -1\,\ (mod\ c)\end{eqnarray}\rm\,\ \Rightarrow\ \ a^{2kn}\equiv 1\,\ (mod\ bc)$
$\endgroup$ $\begingroup$You can use Chinese Remainder Theorem.
Observe that 341 = 11 * 31.
By Fermat's little theorem$$2^{340} \bmod 11 \equiv 2^{10*34} \bmod 11 \equiv 1^34 \bmod 11 \equiv 1 \bmod 11$$$$2^{340} \bmod 31 \equiv 2^{30 * 10 + 10} \bmod 31 \equiv 2^10 \bmod 31 \equiv 32^2 \bmod 31 \equiv 1 \bmod 31$$
$1 \bmod 341$ is one such solution, and it is unique in the integers mod 341 (again by Chinese Remainder Theorem).
$\endgroup$
