We saw in theorem 3.1.3 that when we do arithmetic modulo some number $n$, the answer doesn't depend on which numbers we compute with, only that they are the same modulo $n$. For example, to compute $16\cdot 30\pmod {11}$, we can just as well compute $5\cdot 8\pmod {11}$, since $16\equiv 5$ and $30\equiv 8$. This suggests that we can go further, devising some universe in which there really is no difference between $16$ and $5$ (assuming that we want to work modulo $11$).
Throughout this section, unless otherwise specified, assume all equivalences are modulo $n$, for some fixed but unspecified $n$.
Definition 3.2.1 For every integer $a$, let $[a]$ have the property that $[a] = [a']$ if and only if $a\equiv a'$.
Note that this is a very peculiar definition: we give no hint as to what $[a]$ is—we only specify one aspect of its behavior. This turns out not to matter much, but we will eventually see what $[a]$ "really'' is.
Recall that if $r$ is the remainder on dividing $n$ into $a$, then $a\equiv r$, or, in our new language, $[a]=[r]$. This means that every $[a]$ is equal to some $[r]$ for $0\le r< n$; this motivates the next definition.
Definition 3.2.2 Let $\Z_n=\{[0], [1], [2],…, [n1]\}$.
That is, by the preceding remark, $\Z_n$ consists of all possible $[a]$. This is a new universe in which we can investigate "arithmetic''.
Example 3.2.3 $\Z_4=\{[0], [1], [2], [3]\}$. We could write $\Z_4=\{[80], [25], [102], [13]\}$ instead, but only to make a point—not in practice.
Example 3.2.4 In $\Z_5$, $[1]=[6]=[4]$, $[3] = [8] = [2]$.
Now we're ready to see if we can indeed do arithmetic in this new universe $\Z_n$. We start with the simplest operations, namely, addition, subtraction and multiplication.
Definition 3.2.5 If $[a]$, $[b]\in \Z_n$, let $[a]+[b]=[a+b]$, $[a][b]=[ab]$ and $[a]\cdot[b]=[ab]$.
Most mathematicians would agree that these definitions are natural, even inevitable. You might try to think of other ways that these simple operations might be defined on $\Z_n$.
Example 3.2.6 Here are the addition and multiplication tables for $\Z_4$.


Unfortunately, though we have characterized the definitions of addition, subtraction and multiplication as "natural,'' the situation is not as straightforward as it may first appear. The definition $[a]+[b]=[a+b]$ depends on the manipulation of specific integers $a$ and $b$, but we know that there are other integers $c$ and $d$ with $[a]=[c]$ and $[b]=[d]$. What if we compute $[c+d]$? We had better get the same result as $[a+b]$ or the definition of addition doesn't make sense: $[a]+[b]$ would be different than $[c]+[d]$, but they must be the same. Fortunately, theorem 3.1.3 comes to the rescue, and the two quantities $[a+b]$ and $[c+d]$ are the same. Here's why: since $[a]=[c]$ and $[b]=[d]$, $a$ and $c$ are congruent modulo $n$, as are $b$ and $d$. Therefore their sums $a+b$ and $c+d$ are congruent which means that $[a+b]=[c+d]$. Subtraction and multiplication can be justified in the same way. What we have shown is that the definitions of addition, subtraction and multiplication are "welldefined.''
Many of the familiar algebraic properties of integers carry over to $\Z_n$; here are a few of the most familiar.
a) $[a]+[b]=[b]+[a]$,
b) $[a]+([b] + [c])=([a] +[b])+[c]$,
c) $[a]\cdot[b]=[b]\cdot[a]$,
d) $[a]\cdot([b]\cdot [c])=([a]\cdot [b])\cdot[c]$,
e) $[a]\cdot([b]+[c])=[a]\cdot[b]+[a]\cdot[c]$.
f) $[0]+[a] = [a]$,
g) $[0]\cdot[a]= [0]$,
h) $[1]\cdot[a]= [a]$.
Proof.
We prove two parts and leave the rest as exercises.
Part (a) follows since $[a]+[b]= [a+b]=[b+a]= [b]+[a]$; in other words, we just reduce it to the corresponding statement for regular addition. Similarly (f) follows since $[0] + [a] = [0+a]=[a]$.
Parts (a) and (c) are commutative laws, (b) and (d) are associative laws and (e) says that multiplication distributes over addition. Parts (f), (g) and (h) show that $[0]$ and $[1]$ act in $\Z_n$ in much the same way that $0$ and $1$ act in $\Z$. Though many properties of the integers are shared by $\Z_n$, there are exceptions; here is one.
Example 3.2.8 In $\Z$, if $ab=0$ then either $a$ or $b$ must be 0, but in $\Z_n$ this need not be the case. For example, in $\Z_{12}$, $[3]\cdot[4]= [12]=[0]$, but $[3]\ne [0]$ and $[4] \ne [0]$.
We do not yet know what $[a]$ is, but it certainly is not an integer, so $\Z_n$ is not a subset of $\Z$. Remember this well; it sometimes is tempting to confuse $\Z_n=\{[0], [1], [2],…, [n1]\}$ with $\{0, 1, 2,…, n1\}\subset \Z$. The brackets make all the difference in the world: in $\Z_5$, $[2]=[7]$, but of course $2\not=7$.
Exercises 3.2
Ex 3.2.1 Construct addition and multiplication tables for
Ex 3.2.2 Prove the remaining parts of Theorem 3.2.7.
Ex 3.2.3 If $[a]$ and $[b]$ are in $\Z_n$, prove that there is a unique $[x]\in \Z_n$ such that $[a]+[x]= [b]$.
Ex 3.2.4 Use the table from exercise 1(b) to verify the following statements:
a) There is a unique $[x]\in \Z_6$ such that $[5]\cdot[x]= [2]$
b) There is no $[x]\in \Z_6$ such that $[3]\cdot [x]= [4]$.
c) There is an $[x]\in \Z_6$ such that $[4]\cdot[x]=[2]$, but it is not unique.
Ex 3.2.5 Find all the elements $[x]$ of $\Z_{15}$ such that $[x]=[p]$ for some prime number $p$ ($p$ need not be less than 15).
Ex 3.2.6 Suppose you add together all the elements of $\Z_n$. What is the result?
Ex 3.2.7 In $\Z_{12}$, find all of the elements $[x]$ such that $[x]^n=[0]$ for some positive integer $n$.