Z mod n

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$ .

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.

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''.

$\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$

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.

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$ .

Here are the addition and multiplication tables for $\Z_4$ .

$+$	$[0]$	$[1]$	$[2]$	$[3]$
$[0]$	$[0]$	$[1]$	$[2]$	$[3]$
$[1]$	$[1]$	$[2]$	$[3]$	$[0]$
$[2]$	$[2]$	$[3]$	$[0]$	$[1]$
$[3]$	$[3]$	$[0]$	$[1]$	$[2]$

$\times$	$[0]$	$[1]$	$[2]$	$[3]$
$[0]$	$[0]$	$[0]$	$[0]$	$[0]$
$[1]$	$[0]$	$[1]$	$[2]$	$[3]$
$[2]$	$[0]$	$[2]$	$[0]$	$[2]$
$[3]$	$[0]$	$[3]$	$[2]$	$[1]$

$\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.

In $\Z_n$ ,

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.

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

a) $\Z_2$

b) $\Z_6$ .

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$ .

Collapse menu

1 Logic

2 Proofs

3 Number Theory

4 Functions

5 Relations

6 Bibliography

Exercises 3.2