SI242: New number systems, the integers "mod n"

Mod $n$

Last class we defined quotient and remainder, and we introduced the div(·,·) algorithm that computes them. Of course "div" returns two values. When all we want is the remainder, we often refer to "mod" as an operator that returns just that. So "$x \bmod n$" produces the remainder when dividing $x$ by $n$.

A new kind of number system: $\mathbb{Z}_n$

Let's consider a new kind of number system.

For integer $n$, where $n > 1$, we define the integers mod $n$, often written as $\mathbb{Z}_n$, as the number system with elements $\{0,1,\ldots,n-1\}$ and

$+$ operation defined as: $a+b = \underbrace{a+b}_{\text{as integers}} \bmod n$, and
$*$ operation defined as: $a*b = \underbrace{a*b}_{\text{as integers}} \bmod n$.

Note: "mod $n$" after the integer sum/product guarantees the result is in $\{0,1,\ldots,n-1\}$.

It is easiest to see this as a new number system by considering a concrete example. So consider the $n=3$ case. We can list the elements of $\mathbb{Z}_3$, of course, but we can also build a table for the $+$ and $*$ operators, since there are only three numbers in the number system. Note: In principle, we can do this for any $n$, but of course in practice when $n$ is large this is no longer helpful. To build the tables, of course, we have to go back to the definition of $+$ and $*$ in $\mathbb{Z}_3$ above.

The $\mathbb{Z}_3$ number system

"numbers"
$\{0,1,2\}$

$+$	0	1	2
0	0	1	2
1	1	2	0
2	2	0	1

$*$	1	2
0	0	0
1	1	2
2	2	1

Note: when looking up $a+b$ or $a*b$ in a table, out convention will always be that the first operand ("$a$" in this case) tells you which row to look at, and the second ("$b$" in this case) tells you which column to look at.

So now let us look at some basic arithemtic in this new system.

2 * (2 + 2) + 1  =  2 * 1 + 1   =   2 + 1  = 0
     \___/          \___/           \___/   
      = 1            = 2             = 0          
  (see + table)  (see * table)   (see + atable)

So once we have those tables, we can see that we have a new number system that allows us to do some basic arithmetic without any reference back to the integers ... so this is its own number system.

Really important in-class activity!

Almost the entirety of this class was spent with you folks doing the work, not me, through the in-class ACTIVITY.

Really important out-class activity: Prove $\mathbb{Z}_n$ is a (commutative) ring!

Although proving it is mostly tiresome and obvious, the following is a really important result (recall that a ring is a "commutative ring" if multiplication is commutative):

The integers mod $n$, ie. $\mathbb{Z}_n$, is a commutative ring.

To prove this, we must show that each of the seven ring axioms plus the commutativity of multiplication are satisfied.

1.iii: (additive identity)
Clearly $0 + x = x$ in $\mathbb{Z}_n$ for any $x$.
2.iii: (multiplicative identity)
Clearly $1 * x = x$ in $\mathbb{Z}_n$ for any $x$.
1.iv: (additive inverse)
We need to show that every $x$ in $\mathbb{Z}_n$ has an additive inverse.
Case $x = 0$: then $x + 0 = 0$, so $x$ has an additive inverse.
Case $x \neq 0$: then $0 \lt n - x \lt n$ (over the integers), since $0 \lt x \lt n$. So $n-x$ is an element of $\mathbb{Z}_n$, and $x + (n-x) \bmod n = n \bmod n = 0$. So $x + (n-x) = 0$ in $\mathbb{Z}_n$.

1.ii: (addition is commutative)

over the integers		over $\mathbb{Z}_n$
by division algorithm: $a + b = q\cdot n + r$ $a+b = b+a$ over the integers, so by : $b + a = q\cdot n + r$	→ →	so by definition $a + b = r$ so by definition $b + a = r$ therefore $a + b = b + a$ qed

1.ii: (multiplication is commutative)

over the integers		over $\mathbb{Z}_n$
by division algorithm: $a * b = q\cdot n + r$ $ab = ba$ over the integers, so by : $b * a = q\cdot n + r$	→ →	so by definition $a * b = r$ so by definition $b * a = r$ therefore $a * b = b * a$ qed

1.i: (addition is associative)
The following argument shows that $(a + b) + c$ in $\mathbb{Z}_n$ is $(a + b + c) \bmod n$.

over the integers		over $\mathbb{Z}_n$
by division algorithm: $a + b = q_1\cdot n + r_1$ by division algorithm: $r_1 + c = q_2\cdot n + r_2$ $a + b + c = q_1\cdot n + r_1 + c$ $a + b + c = q_1\cdot n + q_2\cdot n + r_2$ $a + b + c = (q_1 + q_2)\cdot n + r_2$ $(a + b + c) \bmod n = r_2$	→ →	so by definition $a + b = r_1$ so by definition $r_1 + c = (a + b) + c = r_2$

The argument showing that $a + (b + c)$ in $\mathbb{Z}_n$ is $(a + b + c) \bmod n$ is essentially the same. So we get that $(a + b) + c = a + (b + c)$ in $\mathbb{Z}_n$ [both are $(a + b + c) \bmod n$].

2.i: (multiplication is associative)
The following argument shows that $(a * b) *c$ in $\mathbb{Z}_n$ is $(a * b * c) \bmod n$.

over the integers		over $\mathbb{Z}_n$
by division algorithm: $a * b = q_1\cdot n + r_1$ by division algorithm: $r_1 * c = q_2\cdot n + r_2$ $a * b * c = (q_1\cdot n + r_1) * c$ $a * b * c = q_1\cdot n\cdot c + q_2\cdot n + r_2$ $a + b + c = (q_1\cdot c + q_2)\cdot n + r_2$ $(a + b + c) \bmod n = r_2$	→ →	so by definition $a * b = r_1$ so by definition $r_1 * c = (a * b) * c = r_2$

The argument showing that $a * (b * c)$ in $\mathbb{Z}_n$ is $(a * b * c) \bmod n$ is essentially the same. So we get that $(a * b) * c = a * (b * c)$ in $\mathbb{Z}_n$ [both are $(a * b * c) \bmod n$].

3.i: (distributive property)
We first show that $a * (b + c)$ in $\mathbb{Z}_n$ is $a * (b + c) \bmod n$:

over the integers		over $\mathbb{Z}_n$
by division algorithm: $b + c = q_1\cdot n + r_1$ by division algorithm: $a * r_1 = q_2\cdot n + r_2$ $a * (b + c) = a \cdot (q_1\cdot n + r_1)$ $a * (b + c) = a \cdot q_1\cdot n + a\cdot r_1$ $a * (b + c) = a \cdot q_1\cdot n + a\cdot q_2\cdot n + r_2$ $a * (b + c) = (a \cdot q_1 + a\cdot q_2)\cdot n + r_2$	→ →	so by definition $b + c= r_1$ so by definition $a * r_1 = a * (b + c) = r_2$

So $a * (b + c)$ in $\mathbb{Z}_n$ is $a * (b + c) \bmod n$.

We next show that $a * b + a* c$ in $\mathbb{Z}_n$ is $a*b + a*c \bmod n$:

over the integers		over $\mathbb{Z}_n$
by division algorithm: $ab = q_1\cdot n + r_1$ by division algorithm: $a c = q_2\cdot n + r_2$ by division algorithm: $r_1 + r_2 = q_3\cdot n + r_3$ $ab + ac = q_1 n + r_1 + q_2 n + r_2$ $ab + ac = q_1 n + q_2 n + q_3 n + r_3$ $ab + ac = (q_1 + q_2 + q_3) n + r_3$	→ →	so by definition $ab = r_1$ so by definition $a c = r_2$ so by definition $r_1 + r_2 = a * b + a* c = r_3$

So $a * b + a* c$ in $\mathbb{Z}_n$ is $a*b + a*c \bmod n$.

Finally, since $a(b+c) = a*b + a*c$ in the integers, their remainders when dividing by $n$ must be the same, so $a(b + c) = a * b + a* c$ in $\mathbb{Z}_n$

Outside the scope, but interesting and important

These proofs are outside of the scope of this class, but the results are interesting and important, so I am including them here for the interested.
In class, some folks were already beginning to suspect that When faced with a complicated expression in $\mathbb{Z}_n$ to evaluate, we could just evaluate the whole thing over the integers and just "mod n" at the very end and get the same answer. This is in fact true!

We will start off by proving a "lemma", i.e. a little theorem, that will be useful in proving the main result.

Let $n$ be an integer greater than 1. If $x_1$ and $y_1$ are integers with the same remainder mod $n$, i.e. their quotients and remainders satisfy $x_1 = q_1 n + r_1$ and $y_1 = q'_1 n + r_1$, and $x_2$ and $y_2$ are integers with the same remainder mod $n$, i.e. their quotients and remainders satisfy $x_2 = q_2 n + r_2$ and $y_2 = q'_2 n + r_2$, then

$x_1 + x_2$ and $y_1 + y_2$ have the same remainders mod $n$
$x_1 * x_2$ and $y_1 * y_2$ have the same remainders mod $n$
$-x_1$ and $-y_1$ have the same remainders mod $n$

Let $q$ and $r$ be the quotient and remainder of div($r_1 + r_2$, $n$), i.e. $r_1 + r_2 = q n + r$. $$ x_1 + x_2 = q_1 n + r_1 + q_2 n + r_2 = q_1 n + q_2 n + q n + r = (q_1 + q_2 + q) n + r $$ so $x_1 + x_2 \bmod n = r$. $$ y_1 + y_2 = q'_1 n + r_1 + q'_2 n + r_2 = q'_1 n + q'_2 n + q n + r = (q'_1 + q'_2 + q) n + r $$ so $y_1 + y_2 \bmod n = r$.
Let $q$ and $r$ be the quotient and remainder of div($r_1 * r_2$, $n$), i.e. $r_1 * r_2 = q n + r$. $$ x_1 * x_2 = (q_1 n + r_1) * (q_2 n + r_2) = q_1 q_2 n^2 + q_1 n r_2 + q_2 n r_1 + r_1 * r_2 = q_1 q_2 n^2 + q_1 n r_2 + q_2 n r_1 + q n + r = (q_1 q_2 n + q_1 r_2 + q_2 r_1 + q) n + r $$ so $x_1 * x_2 \bmod n = r$. $$ y_1 * y_2 = (q'_1 n + r_1) + (q'_2 n + r_2) = q'_1 q'_2 n^2 + q'_1 n r_2 + q'_2 n r_1 + r_1*r_2 = q'_1 q'_2 n^2 + q'_1 n r_2 + q'_2 n r_1 + q n + r = (q'_1 q'_2 n + q'_1 r_2 + q'_2 r_1 + q) n + r $$ so $y_1 * y_2 \bmod n = r$.
$-x_1 = -q_1 n + -r_1 = (-q_1 - 1) n + (n - r_1)$, so $-x_1 \bmod n = n - r_1$.
$-y_1 = -q'_1 n + -r_1 = (-q'_1 - 1) n + (n - r_1)$, so $-y_1 \bmod n = n - r_1$.

We are going to prove something stronger!

Assume $n$ is an arbitrary but fixed integer greater than 1. Let +, unary - and * have their usual meaning over the integers, but define new operators +', -' and *' where $a +' b = (a + b) \bmod n$, $a *' b = (a * b) \bmod n$ and $-'a = (-a) \bmod n$. Let $G$ and $H$ be fully parenthesized expressions in +,-,*,+',-',*' which, if they differ at all, differ only in whether or not operators have an apostrophe ( $'$ ) after them. [E.g. $H = -5 + (3*'8)$ and $G = -'5 + (3*8)$.] The numbers resulting from evaluating $G$ and $H$ have the same value mod $n$.

We will prove this by induction on the number of operators in $H$ (which must be the same as in $G$), which we call $n$. If $n = 0$, $H$ and $G$ are just numbers, and by the theorem statement must be the same number, so they have the same value mod $n$. So we consider the case $n > 0$. We have two sub-cases:

Sub-case $H$ is $-(A_H)$ or $-'(A_G)$: then by the inductive hypothesis, if $a_h$ is the evaluation of $A_H$ and and $a_g$ is the evaluation of $A_G$, then $a_h$ and $a_g$ have the same remainder mod $n$, and so by , $-(a_h)$ and $-(a_g)$ have the same remainder mod $n$, so $H$ and $G$ have the same remainders mod $n$.

Sub-case $H$ and $G$ have binary operators at the top level: In this case $H = (H_L) \text{op}_H (H_R)$ and $G = (G_L) \text{op}_G (G_R)$, where $H_L$ and $G_L$ differ only in whether or not operators have 's after them, and same for $G_R$ and $H_R$. So by the inductive hypothesis, if $h_l$, $h_r$, $g_l$ and $g_r$ are equal to the result of evaluating $H_L$, $H_R$, $G_L$ and $G_R$, respectively, then $h_l$ and $g_l$ have the same value mod $n$, and $h_r$ and $g_r$ have the same value mod $n$. First we note that for any $x$ and $y$, $x + y$ and $x +' y$ have the same remainder mod $n$ (it is just that the quotient is zero in the second case because the "mod $n$" has already been done. Same for $x * y$ and $x *X' y$. So, by , $h_l \text{op}_H h_r$ and $g_l \text{op}_G g_r$ and have the same value mod $n$.