Prove that $\mathbb{Z}_n$ is closed under multiplication. Two proofs.

215 Views Asked by At

Claim restatement: Let $a_1, a_2, b_1, b_2 \in \mathbb{Z}$ and $n \in \mathbb{N}$, as well as $a_1 \equiv b_1 \mod{n}$ and $a_2 \equiv b_2 \mod{n}$. Then, $a_1a_2\equiv b_1 b_2 \mod{n}$

I always see the same proof for this.

Proof 1:

By the congruence relations, we get $$n | a_i-b_i $$ and we want to show that $$n|a_1a_2 - b_1 b_2$$

$$a_1a_2 - b_1b_2 = a_1a_2 - b_1a_2 + b_1a_2 -b_1b_2=a_2(a_1-b_1)+b_1(a_2-b_2)$$

and because $\mathbb{Z}_n$ is closed under addition, the result follows.

But there's another more straightforward proof, similar to that of closure under addition, that I never see anywhere.

Proof 2:

From the congruence relations, $\exists k_1, k_2 \in \mathbb{Z}$ such that $$a_i = k_i n+b_i$$

Multiplying, we get

$$a_1a_2=(k_1n+b_1)(k_2n+b_2)=k_1k_2n^2+b_1k_2n+b_2k_1n+b_1b_2$$ $$a_1a_2-b_1b_2=k_1k_2n^2+b_1k_2n+b_2k_1n=n(k_1k_2n+b_1k_2+b_2k_1)$$

$$\frac{a_1a_2-b_1b_2}{n} = k_1k_2n+b_1k_2+b_2k_1 \in \mathbb{Z}$$ By closure in $\mathbb{Z}$ under addition and multiplication.

Thus, clearly $$n|a_1a_2-b_1b_2$$

But I never see this second proof. What makes the first one more desirable?

1

There are 1 best solutions below

0
On

For one thing, the first does not use division anywhere, which is good because apriori, modular arithmetic makes sense outside of $\mathbb Q$, i.e: without reference to division at all.

Another reason, is that yours is a restatement in disguise, without reference to extraneous variables.

On the other hand, your proof is over at the penultimate line, since $n \mid (a_1a_2-b_1b_2)$. I'm not sure what being in $\mathbb Z$ has to do with this, so I don't really see the necessity of having those lines, rather than just factoring $n$ out immediately.