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 ?
$\endgroup$ 34 Answers
$\begingroup$Use repeated squaring, for example $30^{32}=((((30^2)^2)^2)^2)^2$ and take mod 77 at each step.
$\endgroup$ 3 $\begingroup$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.
$\endgroup$ 3 $\begingroup$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}$
$\endgroup$ $\begingroup$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$
$\endgroup$
