Prove that $(a \cdot b) \text{ mod } n = ((a \text{ mod } n) \cdot (b \text{ mod } n)) \text{ mod } n$

Question

Prove for all $n \in \mathbb{N}, n >1$ and $a,b \in \mathbb{Z}$ that $$(a \cdot b) \text{ mod } n = ((a \text{ mod } n) \cdot (b \text{ mod } n)) \text{ mod } n$$

I'm not sure if this is a proof but I tried another way this time:

Let $x=a \text{ mod } n$, let $y= b \text{ mod } n$ where $x,y \in \mathbb{Z}$

$\Rightarrow$

$(x \cdot y) \text{ mod } n= (a \cdot b) \text{ mod } n$

Create a "matching" $p,q \in \mathbb{Z}$ such that:

$a=x+pn$ and $b=y+qn$

$\Rightarrow ((x+pn)(y+qn)) \text{ mod } n= (xy+xqn+ypn+pqn^{2}) \text{ mod } n=(xy+n(xq+yp+pqn)) \text{ mod } n = (x \cdot y) \text{ mod } n$

---

I hope this is correct and counts as proof?

Answer 1

Suppose that:

$$\begin{cases} a \mod n = r_a\\ b \mod n = r_b\\ (a \cdot b) \mod n = r\\ \end{cases}$$ or equivalently $$\begin{cases} a = q_a \cdot n + r_a\\ b = q_b \cdot n + r_b\\ a \cdot b = q \cdot n + r\\ \end{cases}.$$

Then:

$$r_a \cdot r_b = (a-q_a \cdot n)\cdot (b-q_b \cdot n) = \\ = a \cdot b - a \cdot q_b \cdot n - b \cdot q_a \cdot n + q_a \cdot q_b \cdot n^2 = \\ = q \cdot n + r - a \cdot q_b \cdot n - b \cdot q_a \cdot n + q_a \cdot q_b \cdot n^2 = \\ = (q + q_a \cdot q_b \cdot n - a \cdot q_b - b \cdot q_a) \cdot n + r.$$

In other words:

$$r_a \cdot r_b = k \cdot n + r \Rightarrow \\ (r_a \cdot r_b) \mod n = r \Rightarrow \\ r = (a \cdot b) \text{ mod } n = ((a \text{ mod } n) \cdot (b \text{ mod } n)) \text{ mod } n .$$