Correct reasoning when proving the multiplication property in modular arithmetic?

Question

I am trying to understand why this rule works: \begin{align*} a \equiv b \pmod c \quad k \equiv j \pmod c \qquad &\implies \qquad ka\equiv jb \pmod c \end{align*}

I saw that the proof is $ka-jb= (a-b)k+b(k-j)$.

Is it correct to say that since: $a-b$ and $k-j$ are multiples of $c$, and when we add them upp (times any constant, in this case, $k$, and $b$) we should get a new multiple of $c$ and it turns out that this is $ka-jb$ (expanding the RHS)?

Answer 1

Let us first prove the identity you stated for clarity's sake.

Observe that $(a-b)k + b(k-j) = ak - bk + bk - bj$.

The middle two terms cancel out, and we are left with just $ak-bj$.

How does this help us?

As you said: We know $a-b$ is a multiple of $c$; so let's write $a-b = nc$.

You also note that $k-j$ is a multiple of $c$; so let's write $k-j = mc$.

Putting the pieces together, we then have:

$$ak - bj = (a-b)k + b(k-j) = nck + bmc = c(nk + bm)$$

Therefore, $ak-bj$ is a multiple of $c$; that is, $ak \equiv bj \mod c$. QED

Answer 2

Yes, that is correct. You might find the follow deconstruction of the proof instructive.

First, note $\, A\equiv a\,\overset{\large\times\,B}\Rightarrow\, \color{#c00}{AB\equiv aB},\,$ by $\,AB-aB \equiv (A-a)B\equiv 0,\,$ by $\,A-a\equiv 0$

Similarly, $\,\ B\equiv b\,\overset{\large\, a\,\times}\Rightarrow\, \color{#0a0}{aB\equiv ab}.\,$ Thus $\,\color{#c00}{AB\equiv a}\color{#0a0}{B\equiv ab}\,\Rightarrow\, AB\equiv ab,\,$ by transitivity of $\,\equiv.\,$

The original proof combines these two proofs into one by inlining the proof of transivity, i.e.

$$\begin{eqnarray} &&\quad\color{#c00}{AB-aB}\,\equiv\, 0\,\equiv\, \color{#0a0}{aB-ab}\\ \Rightarrow &&0\,\equiv\, \color{#c00}{AB}\ \underbrace{\color{#c00}{-\ aB}\, +\color{#0a0}{ aB}}_{\large \equiv\, 0}\color{#0a0}{ - ab}\,\equiv\, AB-ab^{\phantom{I^{I^I}}}\end{eqnarray}$$

which is simply a special case of the general proof of transitivity, i.e.

$\qquad\qquad\quad\ \ \begin{eqnarray} \color{#c00}{x\equiv y},\ \color{#0a0}{y\equiv z}\,\ \Rightarrow && \color{#c00}{x-y}\,\equiv\, 0\,\equiv \color{#0a0}{y-z}\\ \Rightarrow &&\, 0\, \equiv \color{#c00}{x}\ {\underbrace{\color{#c00}{-\ y}\ +\ \color{#0a0}{y}}_{\large \equiv\,0}} \color{#0a0}{- z} \,\equiv\, x-z\end{eqnarray}$

So the "magic" underbraced cancellation amounts simply to an inlined invocation of transitivity.