B. Associativity and Distributivity of Operations in $\mbox{{\bf Z}}_n$

Let $n\in\mbox{{\bf Z}}$ satisfy $n\geq 2$. Let $\mbox{{\bf Z}}_n=\{x\in\mbox{{\bf N}}\colon x<n\}$. Let $\oplus_n$ and $\odot_n$ be the binary operations on $\mbox{{\bf Z}}_n$ defined by

$$\begin{eqnarray*} a\oplus_nb&=&\mbox{ remainder when }a+b\mbox{ is divided by }n,\\ a\odot_nb&=&\mbox{ remainder when }ab\mbox{ is divided by }n. \end{eqnarray*}$$

Thus for all $a,b\in\mbox{{\bf Z}}_n$,

$$a+b=r\cdot n+(a\oplus_n b)\mbox{ for some }r\in\mbox{{\bf N}}.$$ (B.1)

$$a\cdot b=s\cdot n+(a\odot_n b)\mbox{ for some }s\in\mbox{{\bf N}}.$$ (B.2)

We will show that $\oplus_n$ and $\odot_n$ are associative by using the usual properties of addition and multiplication on $\mbox{{\bf Z}}$.

B.3   Lemma. Let $x,y\in\mbox{{\bf Z}}_n$, $q,r\in\mbox{{\bf Z}}$. If $nq+x=nr+y$, then $x=y$ and $q=r$.

Proof:

Case 1. Suppose $y\leq x$. Then by our assumptions,

$$x-y=n(r-q)$$

and

$$0\leq x-y\leq x<n\cdot 1.$$

So

$$0\leq n(r-q)<n\cdot 1.$$

Since $n>0$, it follows that $0\leq r-q<1$ and since $r-q$ is an integer $r-q=0$, so $r=q$. Then $x-y=0$, so $x=y$.

Case 2. If $y>x$, use Case 1 with $y$ and $x$ interchanged. $\mid\!\mid\!\mid$

B.4   Theorem. $\oplus_n$ is associative on $\mbox{{\bf Z}}_n$.

Proof: Let $a,b,c\in\mbox{{\bf Z}}_n$. Then

$$a+b=n\cdot t+(a\oplus_n b)\mbox{ for some }t\in\mbox{{\bf Z}}.$$ (B.5)

$$b+c=n\cdot r+(b\oplus_nc)\mbox{ for some }r\in\mbox{{\bf Z}}.$$ (B.6)

$$(a\oplus_n b)+c=n\cdot s+\left((a\oplus_n b)\oplus_n c\right)\mbox{ for some }s\in\mbox{{\bf Z}}.$$ (B.7)

$$a+(b\oplus_n c)=n\cdot w+(a\oplus_n(b\oplus_n c))\mbox{ for some }w\in\mbox{{\bf Z}}.$$ (B.8)

By adding $c$ to both sides of (B.5), we get

$$(a+b)+c=nt+\left((a\oplus_n b)+c\right),$$ (B.9)

and by adding $a$ to both sides of (B.6), we get

$$a+(b+c)=nr+\left(a+(b\oplus_n c)\right).$$ (B.10)

Replace $(a\oplus_n b)+c$ in (B.9) by its value from (B.7) to get

$$(a+b)+c=n(s+t)+\left((a\oplus_n b)\oplus_n c\right)$$ (B.11)

and replace $a+(b\oplus_n c)$ in (B.10) by its value from (B.8) to get

$$a+(b+c)=n(r+w)+\left(a\oplus_n (b\oplus_n c)\right.)$$ (B.12)

By (B.11) and (B.12) and the associative law in $\mbox{{\bf Z}}$,

$$n(s+t)+\left((a\oplus_n b)\oplus_n c\right)=n(r+w)+\left(a\oplus_n (b\oplus_n c)\right).$$

the associativity of $\oplus_n$ follows from lemma (B.3). $\mid\!\mid\!\mid$

B.13   Theorem. $\odot_n$ is associative on $\mbox{{\bf Z}}_n$.

Proof: The proof is nearly identical with the proof that $\oplus_n$ is associative.

B.14   Theorem. The distributive law holds in $\mbox{{\bf Z}}_n$; i.e., for all $a,b,c\in\mbox{{\bf Z}}_n$,

$$a\odot_n(b\oplus_n c)=(a\odot_n b)\oplus_n(a\odot_n c).$$

Proof: We have

$$b+c=n\cdot t+(b\oplus_n c)\mbox{ for some }t\in\mbox{{\bf Z}}.$$ (B.15)

$$a\cdot(b\oplus_n c)=n\cdot s + \left(a\odot_n(b\oplus_n c)\right)\mbox{ for some }s\in\mbox{{\bf Z}}.$$ (B.16)

$$a\cdot b=n\cdot u+(a\odot_n b)\mbox{ for some }u\in\mbox{{\bf Z}}.$$ (B.17)

$$a\cdot c=n\cdot v+(a\odot_n c)\mbox{ for some }v\in\mbox{{\bf Z}}.$$ (B.18)

Multiply both sides of (B.15) by $a$ to get

$$a\cdot(b+c)=n\cdot at+a\cdot(b\oplus_n c).$$ (B.19)

Replace $a\cdot(b\oplus_n c)$ in (B.19) by its value from (B.16) to get

$$a\cdot(b+c)=n(at+s)+(a\odot_n(b\oplus_n c)).$$ (B.20)

Now add equations (B.17) and (B.18) to get

$$a\cdot b+a\cdot c=n\cdot(u+v)+\left((a\odot_n b)+(a\odot_n c)\right).$$ (B.21)

We know that for some $w\in\mbox{{\bf Z}}$,

$$(a\odot_n b)+(a\odot_n c)=n\cdot w+\left((a\odot_n b)\oplus_n(a\odot_n c)\right),$$

and if we substitute this into (B.21), we obtain

$$a\cdot b+a\cdot c=n(u+v+w)+\left((a\odot_n b)\oplus_n(a\odot_n c)\right).$$ (B.22)

From (B.20) and (B.22) and the distributive law in $\mbox{{\bf Z}}$, we conclude

$$n(at+s)+\left(a\odot_n(b\oplus_n c)\right)=n(u+v+w)+\left((a\odot_n b)\oplus_n(a\odot_n c)\right).$$

The distributive law follows from lemma B.3. $\mid\!\mid\!\mid$