# How to solve $30^{37} \mod 77$ without calculator?

I tried doing something like this: $$(30^2)^{15}(30^7)\mod 77$$ but it is not effective, maybe someone knows some tips and tricks to solve this ?

• Have you heard about the Chinese remainder theorem? It says that because $77 = 7\cdot 11$, where $7$ and $11$ are coprime, you can focus on calculations modulo $7$ and modulo $11$ separately, and put it together to modulo $77$ afterwards. – Arthur Jun 6 '17 at 20:29
• Hint: $30=2\times 3 \times 5$ and $2$, $3$ and $5$ are coprime to $77$ and $\phi(77)=60$ – Amin235 Jun 6 '17 at 20:31
• – Ethan Bolker Jun 6 '17 at 20:36

By Fermat Little Theorem $$30^{6} \equiv 1 \pmod{7} \\ 30^{10} \equiv 1 \pmod{11}$$

Therefore $$30^{37}=(30^6)^6 \cdot 30 \equiv 30\equiv 2 \pmod{7} \\ 30^{37} \equiv 30^7\equiv (-3)^7 \equiv -3^4 \cdot 3^3 \equiv 7 \cdot 5 \equiv 2\pmod{11}$$

This shows that $7,11 |30^{37}-2$ and hence $77 | 30^{37}-2$. Thus $$30^{37}\equiv 2 \pmod{77}$$ unless I made a small mistake in the computations.

• I got the same answer (but you beat me by 19 seconds). – TonyK Jun 6 '17 at 20:43
• @TonyK I know the feeling, happened to me few times in the past too :) – N. S. Jun 6 '17 at 20:43
• @N.S thanks for advice. – Walter White Jun 6 '17 at 20:45

Use repeated squaring, for example $30^{32}=((((30^2)^2)^2)^2)^2$ and take mod 77 at each step.

when confronted with $f(x) \equiv y \pmod {77}$

consider

$f(x) \equiv y \pmod {7}$ and $f(x) \equiv y \pmod {11}$

Fermat's little theorem says that for all prime $p$ and if $p$ does not divide $a$

$a^{p-1} \equiv 1 \pmod p$

$30^{37} \equiv 2 \pmod 7\\ 30^{37} = (-3)^7\equiv 2 \pmod {11}$

$30^{37}\equiv 2 \pmod{77}$

Do the calculation separately modulo $7$ and modulo $11$.

Modulo $7$:

$30^{37}\equiv 2^{37} \equiv 2$

where using Fermat's Little Theorem $2^{36}=(2^6)^6\equiv 1$.

Modulo $11$:

$30^{37}\equiv 8^{37} \equiv 2^{3×37}=2^{111}\equiv 2$

where using Fermat's Little Theorem $2^{110}=(2^{10})^{11}\equiv 1$.

So $30^{37}\equiv 2 \bmod 7$ and $\bmod 11$, thus the Chinese Remainder Theorem gives

$30^{37}\equiv 2 \bmod 77$