How to find Residue of Power Integer

Question

I found congruence like below in various note-

$$ 6^x \equiv 16 \pmod{20}$$

$$ 5^z\equiv 5 \pmod{20}$$

For any $z,x$ (perhaps, I didn't see any other condition).

How residues $16, 5$ are found? What is the general method? Plz show example with proof.

Answer 1

You look for patterns:

• $6\equiv6\pmod{20}$, $6^2\equiv16\pmod{20}$, $6^3\equiv16\pmod{20}$, … In fact, $n>1\implies6^n\equiv16\pmod{20}$;
• actually, $5^n\equiv5\pmod{20}$ for every natural number $n$.

Of course, this can proved by induction. You have $6^2\equiv16\pmod{20}$. Now, take $n\in\mathbb N$ and assume that $6^n\equiv16\pmod{20}$. Then$$6^{n+1}=6^n\times6\equiv16\times6\equiv16\pmod{20}.$$You can apply the same method to the second assertion.

Answer 2

${\rm Using}\ \ \color{#c00}ab\bmod \color{#c00}ac\, =\, \color{#c00}a(\,b\,\bmod\ c)\,\ $ [mod Distributive Law] $ $ to pull out common factor $\,\color{#c00}a$

$\,\ \ \ \ \ \ 5^{\large 1+n}\bmod 20 \,=\, \color{#c00}5(5^{\large n}\bmod\, 4)\ =\ 5(1)$

$\,\ \ \ \ \ \ 6^{\large 2+n}\bmod 20\, =\, \color{#c00}4(9\cdot6^{\Large n}\!\bmod 5) = 4(4\cdot 1)$

Remark $ $ Pulling out the common factor $\color{#c00}a\,$ decreases the modulus, which increases the odds that modular arithmetic simplifies, e.g. above we reduced to a smaller modulus $\,m\,$ where the powers became trivial powers of $\,1,\,$ i.e. $\bmod m\!:\ \color{#0a0}{m\equiv 0}\,\Rightarrow\,(\color{#0a0}m\!+\!1)^{\large n}\equiv 1^{\large n}\equiv 1$. See here for more.

Essentially MDL = Mod Distributive Law can be viewed as a very efficient operational way of applying $ $ CRT = Chinese Remainder Theorem. Follow the link to learn more. The linked questions list there includes over $60$ worked examples for both integers and polynomials (many of which show clearly how much simpler the MDL approach is in practice).