Unable to explain flow of steps in this basic modular expression?

Question

Consider the expresion $(13 + 11)· 18 (\mod 7)$:

$(13+11)· 18 ≡ (6+4)· 4 (\mod 7)$ Note the transition from $(13+11)· > 18$$\implies$ $(6+4)· 4$

$≡ 10 · 4 (\mod 7)$

$≡ 3 · 4 (\mod 7)$ Note the transition from $10 · 4$$\implies$ $3 · 4$

$≡ 12 (\mod 7)$

$≡ 5 (\mod 7)$

$≡ 5$

---

These 2 transitions involve subtracting 7, but in each case they were either the factor( the $10$ going to $7$ in the 2nd transition) or a component of a factor( the $13$ and $11$ going to $6$ and $4$ in first transition).

I would have understood if they subtracted 7 from the product itself( like the $12$ going to $7$ in the final step) because I can intutively understand that the equivalence that both sides have the same remainder when divided by 7 still holds.

I didn't get how this was possible( there wasn't any law/theorem stating you could do that). Few pages down , I saw this corollary:

$ab ≡ [(a \mod n)(b \mod n)](\mod n)$

Is the transitions some result of the corollary or is there some knowledge I'm lacking entirely to explain those transitions?

Answer 1

The corollary is indeed the key! In case we have: $$ a\pmod n=x\\ b\pmod n=y $$ we can write $$ a=pn+x\\ b=qn+y $$ and therefore $$ a\cdot b=pq\cdot n+(py+qx)n+x\cdot y $$ showing that $$ a\cdot b\equiv x\cdot y\pmod n $$ so this establishes the result, which could also be formulated as

When you do modular arithmetics on products, you can reduce each factor first.

---

To clarify why partial reductions will also work, let us prove a slightly different result that $$ a\cdot b\equiv(a+kn)\cdot b\pmod n $$ This can be seen from $$ (a+kn)\cdot b=a\cdot b+bk\cdot n $$ So when $a$ is changed by $kn$ the product is changed by $bk\cdot n$

Changing one factor of a product by a multiple of $n$ changes the product by a multiple of $n$

Answer 2

Let us define a rule and prove its truth.

Let $a, b, c \in \mathbb{N}$ then:

$a = bn+c \implies a \bmod n = c \bmod n$

Proof:

$a \bmod n = (bn+c) \bmod n = (0 + c) \bmod n = c \bmod n$

Now because this is true, we can say:

\begin{equation*} \begin{split} 18(13+11) \bmod 7 & ≡ 18(7+6+7+4) \bmod 7 \\ & ≡ 18(6+4) \bmod 7 \\ & ≡ (14(6+4)+4(6+4)) \bmod 7 \\ & ≡ 4(6+4) \bmod 7 \\& ≡ 40 \bmod 7 \\& ≡ (7*5+5) \bmod 7 \\& ≡ 5 \bmod 7 \end{split} \end{equation*}

Let me know if there is anything I can clarify :)