0
$\begingroup$

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$
  • 2
    $\begingroup$ 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. $\endgroup$ – Arthur Jun 6 '17 at 20:29
  • 2
    $\begingroup$ Hint: $30=2\times 3 \times 5$ and $2$, $3$ and $5$ are coprime to $77$ and $\phi(77)=60$ $\endgroup$ – Amin235 Jun 6 '17 at 20:31
  • 1
    $\begingroup$ Related: math.stackexchange.com/questions/2214567/… $\endgroup$ – Ethan Bolker Jun 6 '17 at 20:36
4
$\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$
  • 1
    $\begingroup$ I got the same answer (but you beat me by 19 seconds). $\endgroup$ – TonyK Jun 6 '17 at 20:43
  • $\begingroup$ @TonyK I know the feeling, happened to me few times in the past too :) $\endgroup$ – N. S. Jun 6 '17 at 20:43
  • $\begingroup$ @N.S thanks for advice. $\endgroup$ – Walter White Jun 6 '17 at 20:45
5
$\begingroup$

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

$\endgroup$
2
$\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$
2
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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