7 Equivalence Relations

7.4 Modular Arithmetic

7.4.1 Beginning Activity 1 (Congruence Modulo 6)

For this activity, we will only use the relation of congruence modulo 6 on the set of integers.

1. Find five different integers $a$ such that $a\equiv 3(mod6)$ and find five different integers $b$ such that $b\equiv 4(mod6)$. That is, find five different integers in [3], the congruence class of 3 modulo 6 and five different integers in [4], the congruence class of 4 modulo 6 .

2. Calculate $s=a+b$ using several values of $a$ in [3] and several values of $b$ in [4] from Part (1). For each sum $s$ that is calculated, find $r$ so that and $s\equiv r(mod6)$. What do you observe?

3. Calculate $p=a\cdot b$ using several values of $a$ in [3] and several values of $b$ in [4] from Part (1). For each product $p$ that is calculated, find $r$ so that and $p\equiv r(mod6)$. What do you observe?

4. Calculate $q=a^2$ using several values of $a$ in [3] from Part (1). For each product $q$ that is calculated, find $r$ so that and $q\equiv r(mod6)$. What do you observe?

7.4.2 Beginning Activity 2 (The Remainder When Dividing by 9)

If $a$ and $b$ are integers with $b>0$, then from the Division Algorithm, we know that there exist unique integers $q$ and $r$ such that

In this activity, we are interested in the remainder $r$. Notice that $r=a-bq$. So, given $a$ and $b$, if we can calculate $q$, then we can calculate $r$.

We can use the "int" function on a calculator to calculate $q$. [The "int" function is the "greatest integer function." If $x$ is a real number, then $\mathrm{int}(x)$ is the greatest integer that is less than or equal to $x$.]

So, in the context of the Division Algorithm, $q=\mathrm{int}\left(\frac{a}{b}\right)$. Consequently,

$$r=a-b\cdot \mathrm{int}\left(\frac{a}{b}\right)$$

If $n$ is a positive integer, we will let $s(n)$ denote the sum of the digits of $n$. For example, if $n=731$, then

$$s(731)=7+3+1=11$$

For each of the following values of $n$, calculate

• The remainder when $n$ is divided by 9, and

• The value of $s(n)$ and the remainder when $s(n)$ is divided by 9.

1. $n=498$

2. $n=7319$

3. $n=4672$

4. $n=9845$

5. $n=51381$

6. $n=305877$

What do you observe?

7.4.3 The Integers Modulo $n$

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

Definition. Let $n\in \mathbb{N}$. The set of congruence classes for the relation of congruence modulo $n$ on $\mathbb{Z}$ is the set of integers modulo $𝒏$, or the set of integers $modn$. We will denote this set of congruence classes by ${\mathbb{Z}}_n$.

Corollary 7.17 tells us that

$$\mathbb{Z}=[0]\cup [1]\cup [2]\cup \mathrm{\cdots }\cup [n-1].$$

In addition, we know that each integer is congruent to precisely one of the integers $0,1,2,\mathrm{\dots },n-1$. This tells us that one way to represent ${\mathbb{Z}}_n$ is

$${\mathbb{Z}}_n=\{[0],[1],[2],\mathrm{\dots },[n-1]\}.$$

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

The set of integers $\mathbb{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 $\mathbb{Z}$, and we know that $\mathbb{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$. For example, in the integers modulo $5,{\mathbb{Z}}_5$, is it possible to add the congruence classes [4] and [2] as follows?

$[4]\oplus [2]$ $=[4+2]$

$=[6]$

$=[1].$

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}$. 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]? The following computation confirms that we do:

$[9]\oplus [7]$ $=[9+7]$

$=[16]$

$=[1].$

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.

If $a\equiv 3(mod6)$ and $b\equiv 4(mod6)$, then - $(a+b)\equiv (3+4)(mod6)$; - $(a\cdot b)\equiv (3\cdot 4)(mod6)$.

If $[a]=[3]$ and $[b]=[4]$ in ${\mathbb{Z}}_6$, then - $[a+b]=[3+4];$ - $[a\cdot b]=[3\cdot 4]$.

These are illustrations of general properties that we have already proved in Theorem 3.28. 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$.

Theorem 3.28. Let $n$ be a natural number and let $a,b,c$, and $d$ be integers. Then

1. If $a\equiv b(modn)$ and $c\equiv d(modn)$, then $(a+c)\equiv (b+d)(modn)$.

2. If $a\equiv b(modn)$ and $c\equiv d(modn)$, then $ac\equiv bd(modn)$.

3. If $a\equiv b(modn)$ and $m\in \mathbb{N}$, then $a^m\equiv b^m(modn)$.

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

Corollary 7.19. Let $n$ be a natural number and let $a,b,c$, and $d$ be integers. Then, in ${\mathbb{Z}}_n$,

1. If $[a]=[b]$ and $[c]=[d]$, then $[a+c]=[b+d]$.

2. If $[a]=[b]$ and $[c]=[d]$, then $[a\cdot c]=[b\cdot d]$.

3. If $[a]=[b]$ and $m\in \mathbb{N}$, then $\left[a^m\right]=\left[b^m\right]$.

Because of Corollary 7.19, 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.

Definition. Let $n\in \mathbb{N}$. Addition and multiplication in ${\mathbb{Z}}_n$ are defined as follows: For $[a],[c]\in {\mathbb{Z}}_n$,

$$[a]\oplus [c]=[a+c]\text{ and }[a]\odot [c]=[ac].$$

The term modular arithmetic is used to refer to the operations of addition and multiplication of congruence classes in the integers modulo $n$.

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

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

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

$$[1]\oplus [2]=[3]=[0].$$

Similarly, by definition, [2] $\odot [2]=[4]$, and in ${\mathbb{Z}}_3,[4]=[1]$. So we write

$$[2]\odot [2]=[4]=[1].$$

The complete addition and multiplication tables for ${\mathbb{Z}}_3$ are

$\oplus$	$[0]$	$[1]$	$[2]$
$[0]$	$[0]$	$[1]$	$[2]$
$[1]$	$[1]$	$[2]$	$[0]$
$[2]$	$[2]$	$[0]$	$[1]$

$\odot$	$[0]$	$[1]$	$[2]$
$[0]$	$[0]$	$[0]$	$[0]$
$[1]$	$[0]$	$[1]$	$[2]$
$[2]$	$[0]$	$[2]$	$[1]$

7.4.4 Progress Check 7.20 (Modular Arithmetic in ${\mathbb{Z}}_2,{\mathbb{Z}}_5$, and ${\mathbb{Z}}_6$)

1. Construct addition and multiplication tables for ${\mathbb{Z}}_2$, the integers modulo 2 .

2. Verify that the following addition and multiplication tables for ${\mathbb{Z}}_5$ are correct.

   $\oplus$	$[0]$	$[1]$	$[2]$	$[3]$	$[4]$
   $[0]$	$[0]$	$[1]$	$[2]$	$[3]$	$[4]$
   $[1]$	$[1]$	$[2]$	$[3]$	$[4]$	$[0]$
   $[2]$	$[2]$	$[3]$	$[4]$	$[0]$	$[1]$
   $[3]$	$[3]$	$[4]$	$[0]$	$[1]$	$[2]$
   $[4]$	$[4]$	$[0]$	$[1]$	$[2]$	$[3]$

   $\odot$	$[0]$	$[1]$	$[2]$	$[3]$	$[4]$
   $[0]$	$[0]$	$[0]$	$[0]$	$[0]$	$[0]$
   $[1]$	$[0]$	$[1]$	$[2]$	$[3]$	$[4]$
   $[2]$	$[0]$	$[2]$	$[4]$	$[1]$	$[3]$
   $[3]$	$[0]$	$[3]$	$[1]$	$[4]$	$[2]$
   $[4]$	$[0]$	$[4]$	$[3]$	$[2]$	$[1]$

3. Construct complete addition and multiplication tables for ${\mathbb{Z}}_6$.

4. In the integers, the following statement is true. We sometimes call this the zero product property for the integers.

   For all $a,b\in \mathbb{Z}$, if $a\cdot b=0$, then $a=0$ or $b=0$.
   Write the contrapositive of the conditional statement in this property.

5. Are the following statements true or false? Justify your conclusions.

   1. For all $[a],[b]\in {\mathbb{Z}}_5$, if $[a]\odot [b]=[0]$, then $[a]=[0]$ or $[b]=[0]$.

   2. For all $[a],[b]\in {\mathbb{Z}}_6$, if $[a]\odot [b]=[0]$, then $[a]=[0]$ or $[b]=[0]$.

7.4.5 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$, 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$. For example, if $n=7319$, then $s(7319)=7+3+1+9=20$. In Beginning Activity 2, we saw that

$$7319\equiv 2(mod9)\text{ and }20\equiv 2(mod9)$$

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:

$$7319=\left(7\times {10}^3\right)+\left(3\times {10}^2\right)+\left(1\times {10}^1\right)+\left(9\times {10}^0\right)$$ (1)

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$. We do this as follows:

$[7319]$ $=\left[\left(7\times {10}^3\right)+\left(3\times {10}^2\right)+\left(1\times {10}^1\right)+\left(9\times {10}^0\right)\right]$

$=\left[7\times {10}^3\right]\oplus \left[3\times {10}^2\right]\oplus \left[1\times {10}^1\right]\oplus \left[9\times {10}^0\right]$

$=\left([7]\odot \left[{10}^3\right]\right)\oplus \left([3]\odot \left[{10}^2\right]\right)\oplus \left([1]\odot \left[{10}^1\right]\right)\oplus ([9]\odot [1])$ (2)

Since ${10}^3\equiv 1(mod9),{10}^2\equiv 1(mod9)$ and $10\equiv 1(mod9)$, we can conclude that $\left[{10}^3\right]=[1],\left[{10}^2\right]=[1]$ and $[10]=[1]$. Hence, we can use these facts and equation (2) to obtain

$[7319]$ $=\left([7]\odot \left[{10}^3\right]\right)\oplus \left([3]\odot \left[{10}^2\right]\right)\oplus ([1]\odot [10])\oplus ([9]\odot [1])$

$=([7]\odot [1])\oplus ([3]\odot [1])\oplus ([1]\odot [1])\oplus ([9]\odot [1])$

$=[7]\oplus [3]\oplus [1]\oplus [9]$

$=[7+3+1+9]$ (3)

Equation (3) 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 (1).

In general, if $n\in \mathbb{N}$, and $n=a_k{a}_{k-1}\mathrm{\cdots }{a}_1{a}_0$ is the decimal representation of $n$, then

$$n=\left(a_k\times {10}^k\right)+\left(a_{k-1}\times {10}^{k-1}\right)+\mathrm{\cdots }+\left(a_1\times {10}^1\right)+\left(a_0\times {10}^0\right)$$

This can also be written using summation notation as follows:

$$n=\sum _{j=0}^k\left(a_j\times {10}^j\right).$$

Using congruence classes for congruence modulo 9, we have

$[n]$ $=\left[\left(a_k\times {10}^k\right)+\left(a_{k-1}\times {10}^{k-1}\right)+\mathrm{\cdots }+\left(a_1\times {10}^1\right)+\left(a_0\times {10}^0\right)\right]$

$=\left[a_k\times {10}^k\right]\oplus \left[a_{k-1}\times {10}^{k-1}\right]\oplus \mathrm{\cdots }\oplus \left[a_1\times {10}^1\right]\oplus \left[a_0\times {10}^0\right]$

$=\left(\left[a_k\right]\odot \left[{10}^k\right]\right)\oplus \left(\left[a_{k-1}\right]\odot \left[{10}^{k-1}\right]\right)\oplus \mathrm{\cdots }$

$\oplus \left(\left[a_1\right]\odot \left[{10}^1\right]\right)\oplus \left(\left[a_0\right]\odot \left[{10}^0\right]\right)$ (4)

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

Proposition 7.21. If $n$ is a nonnegative integer, then ${10}^n\equiv 1(mod9)$, and hence for the equivalence relation of congruence modulo $9,\left[{10}^n\right]=[1]$.

If we let $s(n)$ denote the sum of the digits of $n$, then

$$s(n)=a_k+a_{k-1}+\mathrm{\cdots }+a_1+a_0,$$

Now using equation (4) and Proposition 7.21, we obtain

$[n]$ $=\left(\left[a_k\right]\odot [1]\right)\oplus \left(\left[a_{k-1}\right]\odot [1]\right)\oplus \mathrm{\cdots }\oplus \left(\left[a_1\right]\odot [1]\right)\oplus \left(\left[a_0\right]\odot [1]\right)$

$=\left[a_k\right]\oplus \left[a_{k-1}\right]\oplus \mathrm{\cdots }\oplus \left[a_1\right]\oplus \left[a_0\right]$

$=\left[a_k+a_{k-1}+\mathrm{\cdots }+a_1+a_0\right]$

$=[s(n)]$

This completes the proof of Theorem 7.22.
Theorem 7.22. Let $n\in \mathbb{N}$ and let $s(n)$ denote the sum of the digits of $n$. Then

1. $[n]=[s(n)]$, using congruence classes modulo 9 .

2. $n\equiv s(n)(mod9)$.

3. $9\mid n$ if and only if $9\mid s(n)$.

Part (3) of Theorem 7.22 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 .

7.4.6 Exercises 7.4

1. 1. $(\star )$ Complete the addition and multiplication tables for ${\mathbb{Z}}_4$.

   2. $(\star )$ Complete the addition and multiplication tables for ${\mathbb{Z}}_7$.

   3. Complete the addition and multiplication tables for ${\mathbb{Z}}_8$.

2. The set ${\mathbb{Z}}_n$ contains $n$ elements. One way to solve an equation in ${\mathbb{Z}}_n$ is to substitute each of these $n$ elements in the equation to check which ones are solutions. In ${\mathbb{Z}}_n$, when parentheses are not used, we follow the usual order of operations, which means that multiplications are done first and then additions. Solve each of the following equations:

   1. $(\star )$ ${[x]}^2=[1]$ in ${\mathbb{Z}}_4$

   2. ${[x]}^2=[1]$ in ${\mathbb{Z}}_8$

   3. ${[x]}^4=[1]$ in ${\mathbb{Z}}_5$

   4. ${[x]}^2\oplus [3]\odot [x]=[3]$ in ${\mathbb{Z}}_6$

   5. $(\star )$ ${[x]}^2\oplus [1]=[0]$ in ${\mathbb{Z}}_5$

   6. $[3]\odot [x]\oplus [2]=[0]$ in ${\mathbb{Z}}_5$

   7. $(\star )$ $[3]\odot [x]\oplus [2]=[0]$ in ${\mathbb{Z}}_6$

   8. $[3]\odot [x]\oplus [2]=[0]$ in ${\mathbb{Z}}_9$

3. $(\star )$ In each case, determine if the statement is true or false.

   1. For all $[a]\in {\mathbb{Z}}_6$, if $[a]\ne [0]$, then there exists a $[b]\in {\mathbb{Z}}_6$ such that $[a]\odot [b]=[1]$.

   2. For all $[a]\in {\mathbb{Z}}_5$, if $[a]\ne [0]$, then there exists a $[b]\in {\mathbb{Z}}_5$ such that $[a]\odot [b]=[1]$.

4. In each case, determine if the statement is true or false.

   1. For all $[a],[b]\in {\mathbb{Z}}_6$, if $[a]\ne [0]$ and $[b]\ne [0]$, then $[a]\odot [b]\ne [0]$.

   2. For all $[a],[b]\in {\mathbb{Z}}_5$, if $[a]\ne [0]$ and $[b]\ne [0]$, then $[a]\odot [b]\ne [0]$.

5. 1. $(\star )$ Prove the following proposition:

      For each $[a]\in {\mathbb{Z}}_5$, if $[a]\ne [0]$, then ${[a]}^2=[1]$ or ${[a]}^2=[4]$.

   2. Does there exist an integer $a$ such that $a^2=5,158,232,468,953,153$? Use your work in Part (a) to justify your conclusion. Compare to Exercise (11) in Section 3.5.

6. Use mathematical induction to prove Proposition 7.21.

   If $n$ is a nonnegative integer, then ${10}^n\equiv 1(mod9)$, and hence for the equivalence relation of congruence modulo 9, $\left[{10}^n\right]=[1]$.

7. Use mathematical induction to prove that if $n$ is a nonnegative integer, then ${10}^n\equiv 1(mod3)$. Hence, for congruence classes modulo 3, if $n$ is a nonnegative integer, then $\left[{10}^n\right]=[1]$.

8. Let $n\in \mathbb{N}$ and let $s(n)$ denote the sum of the digits of $n$. So if we write

   $$n=\left(a_k\times {10}^k\right)+\left(a_{k-1}\times {10}^{k-1}\right)+\mathrm{\cdots }+\left(a_1\times {10}^1\right)+\left(a_0\times {10}^0\right)$$

   then $s(n)=a_k+a_{k-1}+\mathrm{\cdots }+a_1+a_0$. Use the result in Exercise (7) to help prove each of the following:

   1. $[n]=[s(n)]$, using congruence classes modulo 3.

   2. $n\equiv s(n)(mod3)$.

   3. $3\mid n$ if and only if $3\mid s(n)$.

9. Use mathematical induction to prove that if $n$ is an integer and $n\ge 1$, then ${10}^n\equiv 0(mod5)$. Hence, for congruence classes modulo 5, if $n$ is an integer and $n\ge 1$, then $\left[{10}^n\right]=[0]$.

10. Let $n\in \mathbb{N}$ and assume

    $$n=\left(a_k\times {10}^k\right)+\left(a_{k-1}\times {10}^{k-1}\right)+\mathrm{\cdots }+\left(a_1\times {10}^1\right)+\left(a_0\times {10}^0\right)$$

    Use the result in Exercise (9) to help prove each of the following:

    1. $[n]=\left[a_0\right]$, using congruence classes modulo 5.

    2. $n\equiv a_0(mod5)$.

    3. $5\mid n$ if and only if $5\mid a_0$.

11. Use mathematical induction to prove that if $n$ is an integer and $n\ge 2$, then ${10}^n\equiv 0(mod4)$. Hence, for congruence classes modulo 4, if $n$ is an integer and $n\ge 2$, then $\left[{10}^n\right]=[0]$.

12. Let $n\in \mathbb{N}$ and assume

    $$n=\left(a_k\times {10}^k\right)+\left(a_{k-1}\times {10}^{k-1}\right)+\mathrm{\cdots }+\left(a_1\times {10}^1\right)+\left(a_0\times {10}^0\right).$$

    Use the result in Exercise (11) to help prove each of the following:

    1. $[n]=\left[10a_1+a_0\right]$, using congruence classes modulo 4.

    2. $n\equiv \left(10a_1+a_0\right)(mod4)$.

    3. $4\mid n$ if and only if $4\mid \left(10a_1+a_0\right)$.

13. Use mathematical induction to prove that if $n$ is an integer and $n\ge 3$, then ${10}^n\equiv 0(mod8)$. Hence, for congruence classes modulo 8, if $n$ is an integer and $n\ge 3$, then $\left[{10}^n\right]=[0]$.

14. Let $n\in \mathbb{N}$ and assume

    $$n=\left(a_k\times {10}^k\right)+\left(a_{k-1}\times {10}^{k-1}\right)+\mathrm{\cdots }+\left(a_1\times {10}^1\right)+\left(a_0\times {10}^0\right)$$

    Use the result in Exercise (13) to help develop a divisibility test for 8. Prove that your divisibility test is correct.

15. Use mathematical induction to prove that if $n$ is a nonnegative integer then ${10}^n\equiv {(-1)}^n(mod11)$. Hence, for congruence classes modulo 11, if $n$ is a nonnegative integer, then $\left[{10}^n\right]=\left[{(-1)}^n\right]$.

16. Let $n\in \mathbb{N}$ and assume

    $$n=\left(a_k\times {10}^k\right)+\left(a_{k-1}\times {10}^{k-1}\right)+\mathrm{\cdots }+\left(a_1\times {10}^1\right)+\left(a_0\times {10}^0\right)$$

    Use the result in Exercise (15) to help prove each of the following:

    1. $n\equiv {\sum }_{j=0}^k{(-1)}^j{a}_j(mod11)$.

    2. $[n]=\left[{\sum }_{j=0}^k{(-1)}^j{a}_j\right]$, using congruence classes modulo 11.

    3. 11 divides $n$ if and only if 11 divides ${\sum }_{j=0}^k{(-1)}^j{a}_j$.

17. 1. $(\star )$ Prove the following proposition:

       For all $[a],[b]\in {\mathbb{Z}}_3$, if ${[a]}^2+{[b]}^2=[0]$, then $[a]=0$ and $[b]=[0]$.

    2. Use Exercise (17a) to prove the following proposition:

       Let $a,b\in \mathbb{Z}$. If $\left(a^2+b^2\right)\equiv 0(mod3)$, then $a\equiv 0(mod3)$ and $b\equiv 0(mod3)$.

    3. Use Exercise (17b) to prove the following proposition:

       For all $a,b\in \mathbb{Z}$, if 3 divides $\left(a^2+b^2\right)$, then 3 divides $a$ and 3 divides $b$.

18. Prove the following proposition:

    For each $a\in \mathbb{Z}$, if there exist integers $b$ and $c$ such that $a=b^4+c^4$, then the units digit of $a$ must be $0,1,2,5,6$, or 7.

19. Is the following proposition true or false? Justify your conclusion.

    Let $n\in \mathbb{Z}$. If $n$ is odd, then $8\mid \left(n^2-1\right)$. Hint: What are the possible values of $n(mod8)$?

20. Prove the following proposition:

    Let $n\in \mathbb{N}$. If $n\equiv 7(mod8)$, then $n$ is not the sum of three squares. That is, there do not exist natural numbers $a,b$, and $c$ such that $n=a^2+b^2+c^2$.

7.4.7 Explorations and Activities

1. Using Congruence Modulo 4. The set ${\mathbb{Z}}_n$ is a finite set, and hence one way to prove things about ${\mathbb{Z}}_n$ is to simply use the $n$ elements in ${\mathbb{Z}}_n$ as the $n$ cases for a proof using cases. For example, if $n\in \mathbb{Z}$, then in ${\mathbb{Z}}_4$, $[n]=[0]$, $[n]=[1],[n]=[2]$, or $[n]=[3]$.

   1. Prove that if $n\in \mathbb{Z}$, then in ${\mathbb{Z}}_4,{[n]}^2=[0]$ or ${[n]}^2=[1]$. Use this to conclude that in ${\mathbb{Z}}_4,\left[n^2\right]=[0]$ or $\left[n^2\right]=[1]$.

   2. Translate the equations $\left[n^2\right]=[0]$ and $\left[n^2\right]=[1]$ in ${\mathbb{Z}}_4$ into congruences modulo 4.

   3. Use a result in Exercise (12) to determine the value of $r$ so that $r\in \mathbb{Z}$, , and

      $$104257833259\equiv r(mod4).$$

      That is, [104 257833 259] $=[r]$ in ${\mathbb{Z}}_4$.

   4. Is the natural number 104257833259 a perfect square? Justify your conclusion.

7.5 Chapter 7 Summary

7.5.1 Important Definitions

• Relation from $A$ to $B$, Section 7.1

• Relation on $A$, Section 7.1

• Domain of a relation, Section 7.1

• Range of a relation, Section 7.1

• Inverse of a relation, Section 7.1

• Reflexive relation, Section 7.2

• Symmetric relation, Section 7.2

• Transitive relation, Section 7.2

• Equivalence relation, Section 7.2

• Equivalence class, Section 7.3

• Congruence class, Section 7.3

• Partition of a set, Section 7.3

• Integers modulo $n$, Section 7.4

• Addition in ${\mathbb{Z}}_n$, Section 7.4

• Multiplication in ${\mathbb{Z}}_n$, Section 7.4

7.5.2 Important Theorems and Results about Relations, Equivalence Relations, and Equivalence Classes

• Theorem 7.6. Let $R$ be a relation from the set $A$ to the set $B$. Then

1. The domain of $R^{-1}$ is the range of $R$. That is, dom $\left(R^{-1}\right)=\mathrm{range}(R)$.

2. The range of $R^{-1}$ is the domain of $R$. That is, $\mathrm{range}\left(R^{-1}\right)=\mathrm{dom}(R)$.

3. The inverse of $R^{-1}$ is $R$. That is, ${\left(R^{-1}\right)}^{-1}=R$.

• Theorem 7.10. Let $n\in \mathbb{N}$ and let $a,b\in \mathbb{Z}$. Then $a\equiv b(modn)$ if and only if $a$ and $b$ have the same remainder when divided by $n$.

• Theorem 7.14. Let $A$ be a nonempty set and let $\sim$ be an equivalence relation on $A$.

1. For each $a\in A,a\in [a]$.

2. For each $a,b\in A,a\sim b$ if and only if $[a]=[b]$.

3. For each $a,b\in A,[a]=[b]$ or $[a]\cap [b]=\mathrm{\varnothing }$.

• Corollary 7.16. Let $n\in \mathbb{N}$. For each $a\in \mathbb{Z}$, let [ $a$ ] represent the congruence class of a modulo $n$.

1. For each $a\in \mathbb{Z},a\in [a]$.

2. For each $a,b\in \mathbb{Z},a\equiv b(modn)$ if and only if $[a]=[b]$.

3. For each $a,b\in \mathbb{Z},[a]=[b]$ or $[a]\cap [b]=\mathrm{\varnothing }$.

• Corollary 7.17. Let $n\in \mathbb{N}$. For each $a\in \mathbb{Z}$, let [a] represent the congruence class of a modulo $n$.

1. $\mathbb{Z}=[0]\cup [1]\cup [2]\cup \mathrm{\cdots }\cup [n-1]$

2. For $j,k\in \{0,1,2,\mathrm{\dots },n-1\}$, if $j\ne k$, then $[j]\cap [k]=\mathrm{\varnothing }$.

• Theorem 7.18. Let $\sim$ be an equivalence relation on the nonempty set $A$. Then the collection $𝒞$ of all equivalence classes determined by $\sim$ is a partition of the set $A$.