-3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Mar 21 '20 at 16:09
  • 1
    $\begingroup$ Fermat's Little Theorem, and the Chinese Remainder theorem. To get started $341 = 31\times 11$ and $31$ and $11$ are both prime. $\endgroup$ – fleablood Mar 21 '20 at 16:10
  • 1
    $\begingroup$ 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$. $\endgroup$ – fleablood Mar 21 '20 at 16:20
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thanks.... Its a silly question. I couldn't get it. $\endgroup$ – Abinash Patra Mar 21 '20 at 16:45
  • 1
    $\begingroup$ it should be 2^10≡1(mod341) instead of 2^10≡1(mod343) Thanks $\endgroup$ – Abinash Patra Mar 21 '20 at 17:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.