Mathematical Reasoning: Writing and Proof (PreTeXt Edition)

Subsection The Integers Modulo \(\boldsymbol{n}\)

Let \(n \in \mathbb{N}\text{.}\) Since the relation of congruence modulo \(n\) is an equivalence relation on \(\mathbb{Z}\text{,}\) we can discuss its equivalence classes. Recall that in this situation, we refer to the equivalence classes as congruence classes.

Corollary 7.21 tells us that

In addition, we know that each integer is congruent to precisely one of the integers \(0, 1, 2, \ldots , n - 1\text{.}\) This tells us that one way to represent \(\mathbb{Z}_{n}\) is

Consequently, even though each integer has a congruence class, the set \(\mathbb{Z}_{n}\) has only \(n\) distinct congruence classes.

The set of integers \(\Z\) is more than a set. We can add and multiply integers. That is, there are the arithmetic operations of addition and multiplication on the set \(\Z\text{,}\) and we know that \(\Z\) is closed with respect to these two operations.

One of the basic problems dealt with in modern algebra is to determine if the arithmetic operations on one set “transfer” to a related set. In this case, the related set is \(\mathbb{Z}_{n}\text{.}\) For example, in the integers modulo 5, \(\Z_5\text{,}\) is it possible to add the congruence classes \([ 4 ]\) and \([ 2 ]\) as follows?

We have used the symbol \(\oplus\) to denote addition in \(\mathbb{Z}_{5}\) so that we do not confuse it with addition in \(\mathbb{Z}\text{.}\) This looks simple enough, but there is a problem. The congruence classes \([ 4 ]\) and \([ 2 ]\) are not numbers, they are infinite sets. We have to make sure that we get the same answer no matter what element of \([ 4 ]\) we use and no matter what element of \([ 2 ]\) we use. For example,

Do we get the same result if we add \([ 9 ]\) and \([ 7 ]\) in the way we did when we added \([ 4 ]\) and \([ 2 ]\text{?}\) The following computation confirms that we do:

This is one of the ideas that was explored in Beginning Activity 1. The main difference is that in this activity, we used the relation of congruence, and here we are using congruence classes. All of the examples in Beginning Activity 1 should have illustrated the properties of congruence modulo 6 in the following table. The left side shows the properties in terms of the congruence relation and the right side shows the properties in terms of the congruence classes.

These are illustrations of general properties that we have already proved in Theorem 3.34. We repeat the statement of the theorem here because it is so important for defining the operations of addition and multiplication in \(\mathbb{Z}_{n}\text{.}\)

Since \(x \equiv y \pmod n\) if and only if \([ x ] = [ y ]\text{,}\) we can restate the result of this Theorem 3.34 in terms of congruence classes in \(\mathbb{Z}_n\text{.}\)

Because of Corollary 7.24, we know that the following formal definition of addition and multiplication of congruence classes in \(\mathbb{Z}_{n}\) is independent of the choice of the elements we choose from each class. We say that these definitions of addition and multiplication are well defined.

So if \(n \in \mathbb{N}\text{,}\) then we have an addition and multiplication defined on \(\mathbb{Z}_n\text{,}\) the integers modulo \(n\text{.}\)

Always remember that for each of the equations in the definitions, the operations on the left, \(\oplus \text{ and } \odot\text{,}\) are the new operations that are being defined. The operations on the right side of the equations \(\left( + \text{ and } \cdot \right)\) are the known operations of addition and multiplication in \(\mathbb{Z}\text{.}\)

Since \(\mathbb{Z}_n\) is a finite set, it is possible to construct addition and multiplication tables for \(\mathbb{Z}_n\text{.}\) In constructing these tables, we follow the convention that all sums and products should be in the form \([ r]\text{,}\) where \(0 \leq r \lt n\text{.}\) For example, in \(\Z_3\text{,}\) we see that by the definition, \([1] \oplus [2] = [3]\text{,}\) but since \(3 \equiv 0 \pmod 3\text{,}\) we see that \([3] = [0]\) and so we write

Similarly, by definition, \([2] \odot [2] = [4]\text{,}\) and in \(\Z_3\text{,}\) \([4] = [1]\text{.}\) So we write

The complete addition and multiplication tables for \(\Z_3\) are

Subsection Divisibility Tests

Congruence arithmetic can be used to prove certain divisibility tests. For example, you may have learned that a natural number is divisible by 9 if the sum of its digits is divisible by 9. As an easy example, note that the sum of the digits of 5823 is equal to \(5 + 8 + 2 + 3 = 18\text{,}\) and we know that 18 is divisible by 9. It can also be verified that 5823 is divisible by 9. (The quotient is 647.) We can actually generalize this property by dealing with remainders when a natural number is divided by 9.

Let \(n \in \mathbb{N}\) and let \(s( n )\) denote the sum of the digits of \(n\text{.}\) For example, if \(n = 7319\text{,}\) then \(s( {7319} ) = 7 + 3 + 1 + 9 = 20\text{.}\) In Beginning Activity 2, we saw that

In fact, for every example in Beginning Activity 2, we saw that \(n\) and \(s( n )\) were congruent modulo 9 since they both had the same remainder when divided by 9. The concepts of congruence and congruence classes can help prove that this is always true.

We will use the case of \(n = 7319\) to illustrate the general process. We must use our standard place value system. By this, we mean that we will write \(7319\) as follows:

The idea is to now use the definition of addition and multiplication in \(\mathbb{Z}_9\) to convert equation (1) to an equation in \(\mathbb{Z}_9\text{.}\) We do this as follows:

Since \(10^3 \equiv 1 \pmod 9\text{,}\) \(10^2 \equiv 1 \pmod 9\) and \(10 \equiv 1 \pmod 9\text{,}\) we can conclude that \([ 10^3 ] = [ 1 ]\text{,}\) \([ {10^2 } ] = [ 1 ]\) and \([ {10} ] = [ 1 ]\text{.}\) Hence, we can use these facts and equation (64) to obtain

Equation (65) tells us that 7319 has the same remainder when divided by 9 as the sum of its digits. It is easy to check that the sum of the digits is 20 and hence has a remainder of 2. This means that when 7319 is divided by 9, the remainder is 2.

To prove that any natural number has the same remainder when divided by 9 as the sum of its digits, it is helpful to introduce notation for the decimal representation of a natural number. The notation we will use is similar to the notation for the number 7319 in equation (63).

In general, if \(n \in \mathbb{N}\text{,}\) and \(n = a_k a_{k - 1} \cdots a_1 a_0\) is the decimal representation of \(n\text{,}\) then

This can also be written using summation notation as follows:

Using congruence classes for congruence modulo 9, we have

One last detail is needed. It is given in Proposition 7.26. The proof by mathematical induction is Exercise 6.

If we let \(s( n )\) denote the sum of the digits of \(n\text{,}\) then

Now using equation (66) and Proposition 7.26, we obtain

This completes the proof of Theorem 7.27.

Item 3 of Theorem 7.27 is called a divisibility test. If gives a necessary and sufficient condition for a natural number to be divisible by 9. Other divisibility tests will be explored in the exercises. Most of these divisibility tests can be proved in a manner similar to the proof of the divisibility test for 9.