# How to find Residue of Power Integer

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.

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.

• that is not a proof. – Consider Non-Trivial Cases Jul 16 '19 at 11:09
• I've edited my answer. What do you think now? – José Carlos Santos Jul 16 '19 at 11:14
• Thank you , appreciate your time Sir – Consider Non-Trivial Cases Jul 16 '19 at 11:41
• @Andrew Such ad-hoc methods will fail miserably for larger numbers. For a much more efficient and more general method see my answer. – Bill Dubuque Jul 16 '19 at 14:31

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