§2.2 Modular Arithmetic

Introduction to Modular Arithmetic

The finite set \(\mathbb{Z}_n\) is closely related to the infinite set \(\mathbb{Z}\). So it is natural to ask if it is possible to define addition and multiplication in \(\mathbb{Z}_n\) and do some reasonable kind of arithmetic there. To define addition in \(\mathbb{Z}_n\), we must have some way of taking two classes in \(\mathbb{Z}_n\) and producing another class—their sum. Because addition of integers is defined, the following tentative definition seems worth investigating:

The sum of the classes \([a]\) and \([c]\) is the class containing \(a + c\), or in symbols:

\([a] ⊕ [c] = [a + c]\),

where addition of classes is denoted by \(\oplus\) to distinguish it from ordinary addition of integers.

We can try a similar tentative definition for multiplication:

The product of \([a]\) and \([c]\) is the class containing \(ac\):

\([a] ⊙ [c] = [ac]\),

where \(\odot\) denotes multiplication of classes.

Example 2.2.1: Modulo 5 Arithmetic

In \(\mathbb{Z}_5\), we have \([3] ⊕ [4] = [3 + 4] = [7] = [2]\) and \([3] ⊙ [2] = [3 \cdot 2] = [6] = [1]\).

Everything seems to work so far, but there is a possible difficulty. Every element of \(\mathbb{Z}_5\) can be written in many different ways. In \(\mathbb{Z}_5\), for instance, \([3] = [13]\) and \([4] = [9]\). In the preceding example, we saw that \([3] ⊕ [4] = [2]\) in \(\mathbb{Z}_5\). Do we get the same answer if we use \([13]\) in place of \([3]\) and \([9]\) in place of \([4]\)? In this case, the answer is "yes" because:

\([13] ⊕ [9] = [13 + 9] = [22] = [2]\).

But how do we know that the answer will be the same no matter which way we write the classes?

To get some idea of the kind of thing that might go wrong, consider these five classes of integers:

• A = \(\{\dots, -14, -8, -2, 0, 6, 12, 18, \dots\}\)
• B = \(\{\dots, -11, -7, -3, 1, 5, 9, 13, \dots\}\)
• C = \(\{\dots, -9, -5, -1, 3, 7, 11, 15, \dots\}\)
• D = \(\{\dots, -16, -10, -4, 2, 8, 14, 20, \dots\}\)
• E = \(\{\dots, -18, -12, -6, 4, 10, 16, 22, \dots\}\)

These classes, like the classes in \(\mathbb{Z}_5\), have the following basic properties: Every integer is in one of them, and any two of them are either disjoint or identical. Since 1 is in B and 7 is in C, we could define \(B + C\) as the class containing \(1 + 7 = 8\), that is, \(B + C = D\). But B is also the class containing \(-3\) and C the class containing 15, and so \(B + C\) ought to be the class containing \(-3 + 15 = 12\). But 12 is in A, so that \(B + C = A\). Thus, you get different answers depending on which "representatives" you choose from the classes B and C. Obviously, you can't have any meaningful concept of addition if the answer is one thing this time and something else another time.

Theorem 2.6: Independence of Class Representatives

If \([a] = [b]\) and \([c] = [d]\) in \(\mathbb{Z}_n\), then:

\([a + c] = [b + d] \quad \text{and} \quad [ac] = [bd]\).

Proof of Theorem 2.6

Since \([a] = [b]\), we know that \(a \equiv b \pmod{n}\) by Theorem 2.3. Similarly, \([c] = [d]\) implies that \(c \equiv d \pmod{n}\). Therefore, by Theorem 2.2:

\(a + c \equiv b + d \pmod{n} \quad \text{and} \quad ac \equiv bd \pmod{n}\).

Hence, by Theorem 2.3 again:

\([a + c] = [b + d] \quad \text{and} \quad [ac] = [bd]\). \(\blacksquare\)

Modular Addition and Multiplication

Addition and multiplication in \(\mathbb{Z}_n\) are defined by:

\([a] \oplus [c] = [a + c] \quad \text{and} \quad [a] \odot [c] = [ac]\).

Example 2: Addition and Multiplication Tables for \(\mathbb{Z}_5\) and \(\mathbb{Z}_6\)

Here are the complete addition and multiplication tables for \(\mathbb{Z}_5\) (verify that these calculations are correct):

These tables are read like this: If \([a]\) appears in the left-hand vertical column and \([c]\) in the top horizontal row of the addition table, for example, then the sum \([a] \oplus [c]\) appears at the intersection of the horizontal row containing \([a]\) and the vertical column containing \([c]\).

Properties of Modular Arithmetic

Now that addition and multiplication are defined in \(\mathbb{Z}_n\), we want to compare the properties of these "miniature arithmetics" with the well-known properties of \(\mathbb{Z}\). The key facts about arithmetic in \(\mathbb{Z}\) (and the usual titles for these properties) are as follows. For all \(a, b, c \in \mathbb{Z}\):

1. If \(a, b \in \mathbb{Z}\), then \(a + b \in \mathbb{Z}\). [Closure for addition]
2. \(a + (b + c) = (a + b) + c\). [Associative addition]
3. \(a + b = b + a\). [Commutative addition]
4. \(a + 0 = a = 0 + a\). [Additive identity]
5. For each \(a \in \mathbb{Z}\), the equation \(a + x = 0\) has a solution in \(\mathbb{Z}\).
6. If \(a, b \in \mathbb{Z}\), then \(ab \in \mathbb{Z}\). [Closure for multiplication]
7. \(a(bc) = (ab)c\). [Associative multiplication]
8. \(a(b + c) = ab + ac\) and \((a + b)c = ac + bc\). [Distributive laws]
9. \(ab = ba\). [Commutative multiplication]
10. \(a \cdot 1 = a = 1 \cdot a\). [Multiplicative identity]
11. If \(ab = 0\), then \(a = 0\) or \(b = 0\).

By using the tables in the preceding example, you can verify that the first ten of these properties hold in \(\mathbb{Z}_5\) and \(\mathbb{Z}_6\) and that Property 11 holds in \(\mathbb{Z}_5\) and fails in \(\mathbb{Z}_6\). But using tables is not a very efficient method of proof (especially for verifying associativity or distributivity). So the proof that Properties 1-10 hold for any \(\mathbb{Z}_n\) is based on the definition of the operations in \(\mathbb{Z}_n\) and on the fact that these properties are known to be valid in \(\mathbb{Z}\).

Theorem 2.7: Properties of Addition and Multiplication in \(\mathbb{Z}_n\)

For any classes \([a], [b], [c]\) in \(\mathbb{Z}_n\):

1. If \([a] \in \mathbb{Z}_n\) and \([b] \in \mathbb{Z}_n\), then \([a] \oplus [b] \in \mathbb{Z}_n\).
2. \([a] \oplus ([b] \oplus [c]) = ([a] \oplus [b]) \oplus [c]\).
3. \([a] \oplus [b] = [b] \oplus [a]\).
4. \([a] \oplus [0] = [a] = [0] \oplus [a]\).
5. For each \([a]\) in \(\mathbb{Z}_n\), the equation \([a] \oplus X = [0]\) has a solution in \(\mathbb{Z}_n\).
6. If \([a] \in \mathbb{Z}_n\) and \([b] \in \(\mathbb{Z}_n\), then \([a] \odot [b] \in \(\mathbb{Z}_n\).
7. \([a] \odot ([b] \odot [c]) = ([a] \odot [b]) \odot [c]\).
8. \([a] \odot ([b] \oplus [c]) = [a] \odot [b] \oplus [a] \odot [c]\) and \(([a] \oplus [b]) \odot [c] = [a] \odot [c] \oplus [b] \odot [c]\).
9. \([a] \odot [b] = [b] \odot [a]\).
10. \([a] \odot [1] = [a] = [1] \odot [a]\).

Proof of Theorem 2.7

Properties 1 and 6 are an immediate consequence of the definition of \(\oplus\) and \(\odot\) in \(\mathbb{Z}_n\).

To prove Property 2, note that by the definition of addition,

\([a] \oplus ([b] \oplus [c]) = [a] \oplus [b + c] = [a + (b + c)]\).

In \(\mathbb{Z}\), we know that \(a + (b + c) = (a + b) + c\). So the classes of these integers must be the same in \(\mathbb{Z}_n\); that is, \([a + (b + c)] = [(a + b) + c]\). By the definition of addition in \(\mathbb{Z}_n\), we have:

\([(a + b) + c] = [a + b] \oplus [c] = ([a] \oplus [b]) \oplus [c]\).

This proves Property 2. The proofs of Properties 3, 7, 8, and 9 are analogous (Exercise 10).

Properties 4 and 10 are proved by direct calculation; for instance,

\([a] \odot [1] = [a \cdot 1] = [a]\).

For Property 5, it is easy to see that \(X = [-a]\) is a solution of the equation since \([a] \oplus [-a] = [a + (-a)] = [0]\). \(\blacksquare\)

Exponents and Equations

The same exponent notation used in ordinary arithmetic is also used in \(\mathbb{Z}_n\). If \([a] \in \mathbb{Z}_n\) and \(k\) is a positive integer, then \([a]^k\) denotes the product

\([a] \odot [a] \odot [a] \odot \cdots \odot [a]\) \((k \text{ factors})\).

Example 2.2.3: Exponents in \(\mathbb{Z}_5\)

In \(\mathbb{Z}_5\), we have:

\([3]^2 = [3] \odot [3] = [4]\) and \([3]^4 = [3] \odot [3] \odot [3] \odot [3] = [1]\).

As noted earlier, the set \(\mathbb{Z}_n\) has exactly \(n\) elements. Consequently, any equation in \(\mathbb{Z}_n\) can be solved by substituting each of these \(n\) elements into the equation to see which ones are solutions.

Example 2.2.4: Solving a Quadratic Equation in \(\mathbb{Z}_6\)

To solve \(x^2 \oplus [5] \odot x = [0]\) in \(\mathbb{Z}_6\), we substitute each of \([0], [1], [2], [3], [4], [5]\) into the equation:

For \([x] = [0]\):
\([0]^2 \oplus [5] \odot [0] = [0] \oplus [0] = [0]\)
Solution: Yes

For \([x] = [1]\):
\([1]^2 \oplus [5] \odot [1] = [1] \oplus [5] = [0]\)
Solution: Yes

For \([x] = [2]\):
\([2]^2 \oplus [5] \odot [2] = [4] \oplus [4] = [2]\)
Solution: No

For \([x] = [3]\):
\([3]^2 \oplus [5] \odot [3] = [3] \oplus [3] = [0]\)
Solution: Yes

For \([x] = [4]\):
\([4]^2 \oplus [5] \odot [4] = [4] \oplus [2] = [0]\)
Solution: Yes

For \([x] = [5]\):
\([5]^2 \oplus [5] \odot [5] = [1] \oplus [1] = [2]\)
Solution: No

So the equation has four solutions: \([0], [1], [3], [4]\).

Example 2.2.4 shows that solving equations in \(\mathbb{Z}_n\) may be quite different from solving equations in \(\mathbb{Z}\). A quadratic equation in \(\mathbb{Z}\) has at most two solutions, whereas the quadratic equation \(x^2 \oplus [5] \odot x = [0]\) has four solutions in \(\mathbb{Z}_6\).