2

How is it possible to solve this without calculator etc.: $$7^{77} \mod 221$$ I started with: \begin{align} 7&\equiv 7 \mod 221 \\ 7^2 &\equiv 49 \mod 221 \\ 7^4 &\equiv \ ? \mod 221 \end{align}

Sure i can calculate this by my own, but is there a trick to calclulate this with any tools?

greedsin
  • 571
  • You can try and find a pattern in the powers of 7 modulo 221, and then apply to the problem – SS_C4 Feb 23 '16 at 12:17

3 Answers3

3

We have $221=13 \cdot 17$, i.e. you should compute

  • $7^{77} \pmod {13}$ (Result will be some $0 \leq a \leq 12$)
  • $7^{77} \pmod {17}$ (Result will be some $0 \leq b \leq 16$)

Afterwards, you use the Chinese Remainder Theorem to find the unique $0 \leq x \leq 220$ with $x \equiv a \pmod {13}$ and $x \equiv b \pmod {17}$.

MooS
  • 31,390
3

Use the Chinese Remainder Theorem. Note that $221=13\times17$. Modulo $13$ we have $$7^2\equiv-3\ ,\quad 7^6\equiv(-3)^3\equiv-1$$ and so $$7^{77}=(7^6)^{12}7^5\equiv7^5=(7^2)(7^2)7\equiv(-3)(-3)7=63\equiv-2\ .$$ Modulo $17$ we have $$7^2\equiv-2\ ,\quad 7^8\equiv(-2)^4\equiv-1$$ and so $$7^{77}=(7^8)^97^5\equiv-7^5\equiv-(-2)(-2)7\equiv6\ .$$ So you have to solve simultaneously $$x\equiv-2\pmod{13}\ ,\quad x\equiv6\pmod{17}\ .$$ Standard methods (look up Chinese Remainder Theorem) give $x\equiv193\pmod{221}$.

David
  • 82,662
2

Without the Chinese Remainder Theorem : $$ \eqalign{ 7^5 &\equiv 11 \pmod {221} \cr 7^{75} &\equiv 11^{15} \pmod {221} \cr 7^{77} &\equiv 7^2 \cdot 11^{15} \pmod {221} \cr } $$ Also $$ \eqalign{ 11^3 &\equiv 5 \pmod {221} \cr 11^{15} &\equiv 5^{5} \pmod {221} \cr } $$ To conclude $$ 7^{77} \equiv 7^2 \cdot 11^{15} \equiv 7^2 \cdot 5^5 \equiv 49 \cdot 31 \equiv 193 $$

nickchalkida
  • 1,495