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'$. $\square$
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],…, [n-1]\}$. $\square$
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. $\square$
Example 3.2.4 In $\Z_5$, $[1]=[6]=[-4]$, $[3] = [8] = [-2]$. $\square$
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]=[a-b]$ and $[a]\cdot[b]=[ab]$. $\square$
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$.
|
|
$\square$
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 "well-defined.''
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]$.$\qed$
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]$. $\square$
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],…, [n-1]\}$ with $\{0, 1, 2,…, n-1\}\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$.