I'm learning modular arithmetic and find the following simplification counter-intuitive.

$21z \equiv 3 \mod 16 \iff 5z \equiv 3 \mod 16$

Of course it's not hard to prove this from scratch:

$$\forall z\; s.t. 21z \equiv 3 \mod 16 \iff \exists k\; s.t. 21z=3+16k \iff 5z=3+16(k-z) \iff 5z \equiv 3 \mod 16$$

However, by counter-intuitive I mean I failed to find this simplification stated explicitly throughout the textbook. Did I miss anything?

  • $\begingroup$ @gotit--thanks So we can substitute all numbers in the LHS with its $\mod 16$, wherever it appears? $\endgroup$ – qweruiop Sep 24 '15 at 15:23
  • $\begingroup$ @gotit--thanks Great. Thanks. Can you move it to the answer panel? $\endgroup$ – qweruiop Sep 24 '15 at 15:28

Here's the way modular numbers work.

Given you're working in $\text{mod} 16$, you can pretend there are only $16$ different numbers (technically, there are $16$ different equivalence classes, but for simplicity let's just call them numbers). We can label them $$0,1,2,\dots, 14,15$$ But this isn't the only way to label them. In fact each different number has an infinite number of pseudonyms. For instance, $0\equiv 16\equiv 32 \equiv -16\mod 16$, where $\equiv$ means that the LHS and RHS are just different names for the same number.

The different names for each of the numbers can be found by adding (or subtracting) some multiple of $16$ to each one. For instance, $4\equiv 20 \equiv -108\mod 16$, because $20=(1)\cdot 16+4$ and $-108=(-8)\cdot 16 +20 = (-7)\cdot 16 +4$.

So you can see that because $5 \equiv 21 \mod 16$, (almost) everywhere you see a $21$ you can just replace it by the number $5$.

Also notice that the $\text{mod} 16$ doesn't just apply to the RHS of the equivalence, it's actually applying to the entire thing. So, $$\begin{align}21z &\equiv 5z \mod 16 \\ \text{means }\ \ \ (21z &\equiv 5z) \mod 16 \\ \text{NOT }\ \ \ 21z &\equiv (5z\mod 16)\end{align}$$


Suppose $21z\equiv 3\pmod{16}$; then $21z-3=16k$, for some integer $k$. Therefore $$ 5z-3=16z+5z-3-16z=16k-16z=16(k-z) $$ and so $5z\equiv3\pmod{16}$.

The converse is almost the same and you should be able to supply it.

In a more abstract way: when you have $a\equiv b\pmod{n}$ and $c\equiv d\pmod{n}$, then $(a+c)\equiv(b+d)\pmod{n}$ and $ac\equiv bd\pmod{n}$.

Since $16\equiv0\pmod{16}$ and, of course, $z\equiv z\pmod{16}$, we have $16z\equiv 0z\pmod{16}$; thus $$ 21z\equiv 5z+16z\equiv 5z+0\equiv 5z\pmod{16} $$ Since congruence modulo $n$ is transitive, saying $21z\equiv3$ is exactly the same as saying $5z\equiv 3$ (modulo $16$).

What's the “intuition”? You can add (or subtract) at will multiples of $16$, when considering congruences modulo $16$.


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.