2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

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

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

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