# Calculate $7^{154} \pmod{341}$ [duplicate]

how to calculate remainder of $$7^ {154}$$ when it is divided by $$341$$. Could you please state which method or theorem to use.

• Hint  By Fermat $\,7^{30}\equiv 1\bmod 11\ \&\ 31,\,$ so also $\!\bmod 341,\,$ so $\bmod 341\!:\ 7^{154}\equiv 7(7^3)\equiv 7(2)\,$ by $\,154\equiv 4\pmod{\!30}$ and modular order reduction. – Bill Dubuque Mar 21 '20 at 16:09
• Fermat's Little Theorem, and the Chinese Remainder theorem. To get started $341 = 31\times 11$ and $31$ and $11$ are both prime. – fleablood Mar 21 '20 at 16:10
• You can also use Eulers theorem and educated guessing with successive squaring. $\phi(341)=\phi(31)\phi(11) = 300$ so $7^{150}$ is probably $\equiv \pm 1\pmod {341}$ and testing $7^k$ were $k|150$ particularly $k=3,5,10$ will likely be useful. $7^2=49$ and $7^3=(50-1)7=350-7=343\equiv 2$. $7^{30}\equiv 1024\equiv 1$. So $7^{150}\equiv 1$. – fleablood Mar 21 '20 at 16:20

Notice, that $$7^3 = 343$$ and $$341*3=1023$$, so $$2^{10} \equiv 1 \pmod{341}$$, then
$$7^{154} \equiv 7 * 2^{51} \equiv 7 * 1 * 2 = 14 \pmod{341}$$