0
$\begingroup$

Most efficient way to do this question?

$25^{37}\cong (mod 55)$

Attempt:

$25^2 \cong 20 (mod55)$

Then I don't know the best way to continue... I know how to brute force it but I'm just curious what the best way is?

$\endgroup$
  • $\begingroup$ Do you know the method of repeated/successive squares? $\endgroup$ – Randall Oct 27 '17 at 2:20
1
$\begingroup$

First, $55 = 5 \cdot 11$ and $(5,11) = 1$, so we will use the Chinese remainder theorem to assemble the result after working modulo $5$ and $11$, separately.

Modulo $5$, $25 \cong 0$, so $25^{37} \cong 0 \pmod{5}$.

Modulo $11$, $25 \cong 3$ and (using Fermat's little theorem) $37 \cong 7 \pmod{10}$, so we compute $$ 25^{37} \cong 3^{37} \cong 3^7 \pmod{11} \text{.} $$ Then \begin{align*} 3^{7} &\cong 3^8 \cdot 3^{-1} \pmod{11} \\ &\cong ((3^2)^2)^2 \cdot 3^{-1} \pmod{11} \\ &\cong (9^2)^2 \cdot 3^{-1} \pmod{11} \\ &\cong 4^2 \cdot 3^{-1} \pmod{11} \\ &\cong 5 \cdot 3^{-1} \pmod{11} \\ &\cong 5 \cdot 4 \pmod{11} \\ &\cong 9 \pmod{11} \text{.} \end{align*}

Then, using the CRT, we want a multiple of $5$ that is congruent to $9$ modulo $11$. Check sequentially: $5$, $10$, $15$, $20$. We find that $20$ works. (There are direct methods, but it's easy to work through the (at most) eleven multiples of $5$.)

Our answer is $25^{37} \cong 20 \pmod{55}$.

$\endgroup$
1
$\begingroup$

You can use the Chinese Remainder Theorem, and Fermat's Little Theorem. Observe that $55=5\times 11$. Clearly $25^{37}\equiv0\pmod5$. Also $$25^{37}=5^{74}\equiv 5^4=25^2\equiv 3^2\equiv 9\pmod{11}$$ using $5^{10}\equiv1\pmod{11}$ (Fermat's Little Theorem). Using the Chinese Remainder Theorem one gets $25^{37}\equiv20\pmod{55}$.

$\endgroup$
1
$\begingroup$

This answer is not as slick as the answers posted before mine. But, this technique works for incredibly large powers even when you do NOT know how the modulus factors...

$37 = 1 + 4 + 32 = 2^0 + 2^2 + 2^5$ so record $25^{2^k} \bmod 55$ for $k=0, 1, \ldots, 5$, but get it by repeated squaring, which is fast: $25^{2^{k+1}}=(25^{2^k})^2$. Get, in order, $$ 25, 20, 15, 5, 25, 20. $$ Now multiply the entries corresponding to $k=0, 2, 5$ to get $$ 25 \cdot 15 \cdot 20 = 20. $$ Hence $25^{37} = 20 \bmod 55$.

$\endgroup$
0
$\begingroup$

$$25^{37}=5^{74}$$

Now as $(5^n,55)=5$ for $n\ge1$

$$5^{74-1}\equiv5^{73\pmod{\phi(55/5)}}\pmod{55/5}$$

$$\implies5^{73}\equiv5^3\equiv4\pmod{11}$$

$$\implies5\cdot5^{73}\equiv5\cdot4\pmod{5\cdot11}$$

$\endgroup$
0
$\begingroup$

Note $\,5^{\large 74} \bmod 55 = \overbrace{5(5^{\large 3}(\color{#c00}{5^{\large 10}})^{\large 7} \bmod 11)}^{\Large 1\ \equiv\ \color{#c00}{5^{\Large 10}} \ {\rm by \ Euler}} = 5(4)\ $

using $\,\ ab\bmod ac = a(b\bmod c) =$ mod Distributive Law to pull a factor of $\,5\,$ out of the $\!\bmod$

$\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.