Solve a congruence $1978^{20}\equiv x\pmod{125}$

Question

I have checked the solution ($x=26$).

Solving modulo $5$ gives $$1978^{20}\equiv 1978^{2\cdot 10}\equiv 1\pmod{5}$$

Solving modulo $25$ also gives $$1978^{20}\equiv 1\pmod{5}$$

How to evaluate the remainder $x$?

Answer 1

As $(ab)\mod c = (a \mod c) (b \mod c)\mod c$ you can say

$$1978^{20}\mod 125$$ $$\equiv (1978\mod 125 )^{20} \mod 125$$ $$\equiv 103^{20} \mod 125 $$ $$\equiv (-22)^{20} \mod 125$$

And as the exponent is even

$$\equiv 22^{20} \mod 125$$

Then you just calculate and take modulo after each calculation. Whenever you hit a low number, you can split the exponent, for example:

$$22^{2} \equiv 484 \equiv 109\equiv -16\mod 125$$

Therefore

$$22^{20} \equiv (22^{2})^{10} \equiv (-16)^{10} \equiv 16^{10}\mod 125$$

You can do the same thing for $16^{10}\mod 125$. This step should give you a number that is pretty small and therefore easy to calculate with.

---

edit: If I interpret your post right, you evaluated the expression $\mod 5$ and $\mod 25$ and wonder why both results multiplied together don't give you the result $\mod 125$. This method does not work.

Say $x \equiv a \mod n$ and $x \equiv b \mod m$

$\implies x = k_1n + a$ and $\implies x = k_2m + b$

However, you can't form this into

$x = k_3(nm) + c \implies x \equiv c \mod (nm)$

Answer 2

Alternative solution:

$1978^1\equiv103\pmod{125}\implies$

$1978^2\equiv103^2\equiv109\pmod{125}\implies$

$1978^4\equiv109^2\equiv6\pmod{125}\implies$

$1978^8\equiv6^2\equiv36\pmod{125}\implies$

$1978^{16}\equiv36^2\equiv46\pmod{125}$

---

$1978^{20}=1978^{4+16}=1978^4\cdot1978^{16}\equiv6\cdot46\equiv26\pmod{125}$

Answer 3

${\rm mod}\ \ \ 25\!:\ \ \ 1978^{\large 4}\equiv 3^{\large 4}\equiv 6,\ $ so $\ 1978^{\large 4} = 6+25j$

${\rm mod}\ 125\!:\ (1978^{\large 4})^{\large 5} \equiv (6+25j)^{\large 5} \equiv 6^{\large 5} + 125(\cdots)\equiv 6^{\large 5}\equiv 26\ $ by the Binomial Theorem

Answer 4

Note that, modulo $125$, $11^2=121\equiv-4$ and $2^7=128\equiv3$.

Therefore, $1978^{20}\equiv(-22)^{20}\equiv 2^{20}11^{20}\equiv 2^{20}(-4)^{10}\equiv 2^{40}\equiv2^{35}2^5\equiv3^52^5\equiv6^5\equiv26$.