Modular Arithmetic

Section 7.4 Modular Arithmetic

Beginning Activity Beginning Activity 1: Congruence Modulo 6
A4 US

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 (\mod 6)$ and find five different integers $b$ such that $b \equiv 4 (\mod 6) .$ 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 Exercise 1. For each sum $s$ that is calculated, find $r$ so that $0 \leq r < 6$ and $s \equiv r (\mod 6) .$ 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 Exercise 1. For each product $p$ that is calculated, find $r$ so that $0 \leq r < 6$ and $p \equiv r (\mod 6) .$ What do you observe?

🔗

4.

Calculate $q = a^{2}$ using several values of $a$ in $[3]$ from Exercise 1. For each product $q$ that is calculated, find $r$ so that $0 \leq r < 6$ and $q \equiv r (\mod 6) .$ What do you observe?

🔗

Beginning Activity Beginning Activity 2: The Remainder When Dividing by 9
A4 US

🔗

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

a = b q + r and 0 \leq r < b .

🔗

In this activity, we are interested in the remainder

r .

Notice that

r = a - b q .

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

int (x)

is the greatest integer that is less than or equal to

x .

]

🔗

So, in the context of the Division Algorithm,

q = int (\frac{a}{b}) .

Consequently,

r = a - b \cdot int (\frac{a}{b}) .

🔗

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?

🔗

Subsection The Integers Modulo $n$

🔗

Let

n \in N .

Since the relation of congruence modulo

n

is an equivalence relation on

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 N .$ The set of congruence classes for the relation of congruence modulo $n$ on $Z$ is the set of integers modulo $n$ , or the set of integers mod $n .$ We will denote this set of congruence classes by $Z_{n} .$

🔗

Corollary 7.21 tells us that

Z = [0] \cup [1] \cup [2] \cup \dots \cup [n - 1] .

🔗

In addition, we know that each integer is congruent to precisely one of the integers

0, 1, 2, \dots, n - 1 .

This tells us that one way to represent

Z_{n}

Z_{n} = {[0], [1], [2], \dots, [n - 1]} .

🔗

Consequently, even though each integer has a congruence class, the set

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,

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

Z_{n} .

For example, in the integers modulo 5,

Z_{5},

is it possible to add the congruence classes

[4]

and

[2]

as follows?

\begin{aligned} \oplus [2] & = [4 + 2] \\ = [6] \\ = [1] . \end{aligned}

🔗

We have used the symbol

\oplus

to denote addition in

Z_{5}

so that we do not confuse it with addition in

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,

\begin{aligned} 9 & \equiv 4 (\mod 5) & and so & [9] = [4] . Also, \\ 7 & \equiv 2 (\mod 5) & and so & [7] = [2] . \end{aligned}

🔗

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:

\begin{aligned} \oplus [7] & = [9 + 7] \\ = [16] \\ = [1] . \end{aligned}

🔗

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 (\mod 6)$ and $b \equiv 4 (\mod 6),$ then

$(a + b) \equiv (3 + 4) (\mod 6);$
$(a \cdot b) \equiv (3 \cdot 4) (\mod 6) .$

If $[a] = [3]$ and $[b] = [4]$ in $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.34. We repeat the statement of the theorem here because it is so important for defining the operations of addition and multiplication in

Z_{n} .

🔗

Theorem 3.34 Restated.

🔗

Let

n

be a natural number and let

a, b, c, and d

be integers. Then

If $a \equiv b (\mod n)$ and $c \equiv d (\mod n),$ then $(a + c) \equiv (b + d) (\mod n) .$
If $a \equiv b (\mod n)$ and $c \equiv d (\mod n),$ then $a c \equiv b d (\mod n) .$
If $a \equiv b (\mod n)$ and $m \in N,$ then $a^{m} \equiv b^{m} (\mod n) .$

🔗

Since

x \equiv y (\mod n)

if and only if

[x] = [y],

we can restate the result of this Theorem 3.34 in terms of congruence classes in

Z_{n} .

🔗

Corollary 7.24.

Let $n$ be a natural number and let $a, b, c,$ and $d$ be integers. Then, in $Z_{n},$

If $[a] = [b]$ and $[c] = [d],$ then $[a + c] = [b + d] .$
If $[a] = [b]$ and $[c] = [d],$ then $[a \cdot c] = [b \cdot d] .$
If $[a] = [b]$ and $m \in N,$ then $[a^{m}] = [b^{m}] .$

🔗

Because of Corollary 7.24, we know that the following formal definition of addition and multiplication of congruence classes in

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 N .$ Addition and multiplication in $Z_{n}$ are defined as follows: For $[a], [c] \in Z_{n},$

[a] \oplus [c] = [a + c] and [a] ⊙ [c] = [a c] .

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 N,

then we have an addition and multiplication defined on

Z_{n},

the integers modulo

n .

🔗

Always remember that for each of the equations in the definitions, the operations on the left,

\oplus and ⊙,

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

Z .

🔗

Since

Z_{n}

is a finite set, it is possible to construct addition and multiplication tables for

Z_{n} .

In constructing these tables, we follow the convention that all sums and products should be in the form

[r],

where

0 \leq r < n .

For example, in

Z_{3},

we see that by the definition,

[1] \oplus [2] = [3],

but since

3 \equiv 0 (\mod 3),

we see that

[3] = [0]

and so we write

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

🔗

Similarly, by definition,

[2] ⊙ [2] = [4],

and in

Z_{3},

[4] = [1] .

So we write

[2] ⊙ [2] = [4] = [1] .

🔗

The complete addition and multiplication tables for

Z_{3}

are

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

$⊙$	$[0]$	$[1]$	$[2]$
$[0]$	$[0]$	$[0]$	$[0]$
$[1]$	$[0]$	$[1]$	$[2]$
$[2]$	$[0]$	$[2]$	$[1]$

🔗

Progress Check 7.25. Modular Arithmetic in $Z_{2},$ $Z_{5},$ and $Z_{6}$ .

🔗

(a)

Construct addition and multiplication tables for $Z_{2},$ the integers modulo 2.

Solution.

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

$⊙$	$[0]$	$[1]$
$[0]$	$[0]$	$[0]$
$[1]$	$[0]$	$[1]$

🔗

(b)

Verify that the following addition and multiplication tables for $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]$

$⊙$	$[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]$

🔗

(c)

Construct complete addition and multiplication tables for $Z_{6} .$

Solution.

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

$⊙$	$[0]$	$[1]$	$[2]$	$[3]$	$[4]$	$[5]$
$[0]$	$[0]$	$[0]$	$[0]$	$[0]$	$[0]$	$[0]$
$[1]$	$[0]$	$[1]$	$[2]$	$[3]$	$[4]$	$[5]$
$[2]$	$[0]$	$[2]$	$[4]$	$[0]$	$[2]$	$[4]$
$[3]$	$[0]$	$[3]$	$[0]$	$[3]$	$[0]$	$[3]$
$[4]$	$[0]$	$[4]$	$[2]$	$[0]$	$[4]$	$[2]$
$[5]$	$[0]$	$[5]$	$[4]$	$[3]$	$[2]$	$[1]$

🔗

(d)

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

For all $a, b \in Z,$ if $a \cdot b = 0,$ then $a = 0$ or $b = 0 .$

Write the contrapositive of the conditional statement in this property.

Solution.

For all $a, b \in Z,$ if $a \neq 0$ and $b \neq 0,$ then $a b \neq 0 .$

🔗

(e)

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

🔗

(i)

For all $[a], [b] \in Z_{5},$ if $[a] ⊙ [b] = [0],$ then $[a] = [0]$ or $[b] = [0] .$

Solution.

The statement in (i) is true.

🔗

(ii)

For all $[a], [b] \in Z_{6},$ if $[a] ⊙ [b] = [0],$ then $[a] = [0]$ or $[b] = [0] .$

Solution.

The statement in (ii) is false. For example, in $Z_{6},$ $[2] ⊙ [3] = [0] .$

🔗

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,

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 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 (\mod 9) and 20 \equiv 2 (\mod 9) .

🔗

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:

\begin{matrix} (63) & 7319 = (7 \times 10^{3}) + (3 \times 10^{2}) + (1 \times 10^{1}) + (9 \times 10^{0}) . \end{matrix}

🔗

The idea is to now use the definition of addition and multiplication in

Z_{9}

to convert equation (1) to an equation in

Z_{9} .

We do this as follows:

\begin{aligned} = [(7 \times 10^{3}) + (3 \times 10^{2}) + (1 \times 10^{1}) + (9 \times 10^{0})] \\ = [7 \times 10^{3}] \oplus [3 \times 10^{2}] \oplus [1 \times 10^{1}] \oplus [9 \times 10^{0}] \\ (64) & = ([7] ⊙ [10^{3}]) \oplus ([3] ⊙ [10^{2}]) \oplus ([1] ⊙ [10^{1}]) \oplus ([9] ⊙ [1]) \end{aligned}

🔗

Since

10^{3} \equiv 1 (\mod 9),

10^{2} \equiv 1 (\mod 9)

and

10 \equiv 1 (\mod 9),

we can conclude that

[10^{3}] = [1],

[10^{2}] = [1]

and

[10] = [1] .

Hence, we can use these facts and equation (64) to obtain

\begin{aligned} [7319] & = ([7] ⊙ [10^{3}]) \oplus ([3] ⊙ [10^{2}]) \oplus ([1] ⊙ [10]) \oplus ([9] ⊙ [1]) \\ = ([7] ⊙ [1]) \oplus ([3] ⊙ [1]) \oplus ([1] ⊙ [1]) \oplus ([9] ⊙ [1]) \\ = [7] \oplus [3] \oplus [1] \oplus [9] \\ (65) & = [7 + 3 + 1 + 9] \end{aligned}

🔗

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 N,

and

n = a_{k} a_{k - 1} \dots a_{1} a_{0}

is the decimal representation of

n,

then

n = (a_{k} \times 10^{k}) + (a_{k - 1} \times 10^{k - 1}) + \dots + (a_{1} \times 10^{1}) + (a_{0} \times 10^{0}) .

🔗

This can also be written using summation notation as follows:

n = \sum_{j = 0}^{k} (a_{j} \times 10^{j}) .

🔗

Using congruence classes for congruence modulo 9, we have

\begin{aligned} = [(a_{k} \times 10^{k}) + (a_{k - 1} \times 10^{k - 1}) + \dots + (a_{1} \times 10^{1}) + (a_{0} \times 10^{0})] \\ = [a_{k} \times 10^{k}] \oplus [a_{k - 1} \times 10^{k - 1}] \oplus \dots \oplus [a_{1} \times 10^{1}] \oplus [a_{0} \times 10^{0}] \\ = ([a_{k}] ⊙ [10^{k}]) \oplus ([a_{k - 1}] ⊙ [10^{k - 1}]) \oplus \dots \\ (66) & \oplus ([a_{1}] ⊙ [10^{1}]) \oplus ([a_{0}] ⊙ [10^{0}]) \end{aligned}

🔗

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

🔗

Proposition 7.26.

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

🔗

If we let

s (n)

denote the sum of the digits of

n,

then

s (n) = a_{k} + a_{k - 1} + \dots + a_{1} + a_{0},

🔗

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

\begin{aligned} [n] & = ([a_{k}] ⊙ [1]) \oplus ([a_{k - 1}] ⊙ [1]) \oplus \dots \oplus ([a_{1}] ⊙ [1]) \oplus ([a_{0}] ⊙ [1]) \\ = [a_{k}] \oplus [a_{k - 1}] \oplus \dots \oplus [a_{1}] \oplus [a_{0}] \\ = [a_{k} + a_{k - 1} + \dots + a_{1} + a_{0}] . \\ = [s (n)] . \end{aligned}

🔗

This completes the proof of Theorem 7.27.

🔗

Theorem 7.27.

Let $n \in N$ and let $s (n)$ denote the sum of the digits of $n .$ Then

$[n] = [s (n)],$ using congruence classes modulo 9.
$n \equiv s (n) (\mod 9) .$
$9 ∣ n$ if and only if $9 ∣ s (n) .$

🔗

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.

🔗

Exercises Exercises

🔗

1.

Complete the addition and multiplication tables for the following.

🔗

(a)

$Z_{4} .$

Answer.

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

$⊙$	$[0]$	$[1]$	$[2]$	$[3]$
$[0]$	$[0]$	$[0]$	$[0]$	$[0]$
$[1]$	$[0]$	$[1]$	$[2]$	$[3]$
$[2]$	$[0]$	$[2]$	$[0]$	$[2]$
$[3]$	$[0]$	$[3]$	$[2]$	$[1]$

🔗

(b)

$Z_{7} .$

Answer.

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

$⊙$	$[0]$	$[1]$	$[2]$	$[3]$	$[4]$	$[5]$	$[6]$
$[0]$	$[0]$	$[0]$	$[0]$	$[0]$	$[0]$	$[0]$	$[0]$
$[1]$	$[0]$	$[1]$	$[2]$	$[3]$	$[4]$	$[5]$	$[6]$
$[2]$	$[0]$	$[2]$	$[4]$	$[6]$	$[1]$	$[3]$	$[5]$
$[3]$	$[0]$	$[3]$	$[6]$	$[2]$	$[5]$	$[1]$	$[4]$
$[4]$	$[0]$	$[4]$	$[1]$	$[5]$	$[2]$	$[6]$	$[3]$
$[5]$	$[0]$	$[5]$	$[3]$	$[1]$	$[6]$	$[4]$	$[2]$
$[6]$	$[0]$	$[6]$	$[5]$	$[4]$	$[3]$	$[2]$	$[1]$

🔗

(c)

$Z_{8} .$

🔗

2.

The set $Z_{n}$ contains $n$ elements. One way to solve an equation in $Z_{n}$ is to substitute each of these $n$ elements in the equation to check which ones are solutions. In $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:

🔗

(a)

$[x]^{2} = [1]$ in $Z_{4}$

Answer.

$[x] = [1]$ or $[x] = [3]$

🔗

(b)

$[x]^{2} = [1]$ in $Z_{8}$

🔗

(c)

$[x]^{4} = [1]$ in $Z_{5}$

🔗

(d)

$[x]^{2} \oplus [3] ⊙ [x] = [3]$ in $Z_{6}$

🔗

(e)

$[x]^{2} \oplus [1] = [0]$ in $Z_{5}$

Answer.

$[x] = [2]$ or $[x] = [3]$

🔗

(f)

$[3] ⊙ [x] \oplus [2] = [0]$ in $Z_{5}$

🔗

(g)

$[3] ⊙ [x] \oplus [2] = [0]$ in $Z_{6}$

Answer.

The equation has no solution.

🔗

(h)

$[3] ⊙ [x] \oplus [2] = [0]$ in $Z_{9}$

🔗

3.

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

🔗

(a)

For all $[a] \in Z_{6},$ if $[a] \neq [0],$ then there exists a $[b] \in Z_{6}$ such that $[a] ⊙ [b] = [1] .$

Answer.

The statement is false. By using the multiplication table for $Z_{6},$ we see that a counterexample is $[a] = [2] .$

🔗

(b)

For all $[a] \in Z_{5},$ if $[a] \neq [0],$ then there exists a $[b] \in Z_{5}$ such that $[a] ⊙ [b] = [1] .$

Answer.

The statement is true. By using the multiplication table for $Z_{5},$ we see that:

\begin{aligned} [1] & ⊙ [1] = [1] . & [2] & ⊙ [3] = [1] \\ [3] & ⊙ [2] = [1] . & [4] & ⊙ [4] = [1] \end{aligned}

🔗

4.

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

🔗

(a)

For all $[a], [b] \in Z_{6},$ if $[a] \neq [0]$ and $[b] \neq [0],$ then $[a] ⊙ [b] \neq [0] .$

🔗

(b)

For all $[a], [b] \in Z_{5},$ if $[a] \neq [0]$ and $[b] \neq [0],$ then $[a] ⊙ [b] \neq [0] .$

🔗

5.

Complete the following.

🔗

(a)

Prove the following proposition:

For each $[a] \in Z_{5},$ if $[a] \neq [0],$ then $[a]^{2} = [1]$ or $[a]^{2} = [4] .$

Answer.

The proof consists of the following computations:

\begin{aligned} [1]^{2} & = [1] \\ [2]^{2} & = [4] \\ [3]^{2} & = [9] = [4] \\ [4]^{2} & = [16] = [1] \end{aligned}

🔗

(b)

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

🔗

6.

Use mathematical induction to prove Proposition 7.26.

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

🔗

7.

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

🔗

8.

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

n = (a_{k} \times 10^{k}) + (a_{k - 1} \times 10^{k - 1}) + \dots + (a_{1} \times 10^{1}) + (a_{0} \times 10^{0}),

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

🔗

(a)

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

🔗

(b)

$n \equiv s (n) (\mod 3) .$

🔗

(c)

$3 ∣ n$ if and only if $3 ∣ s (n) .$

🔗

9.

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

🔗

10.

Let $n \in N$ and assume

n = (a_{k} \times 10^{k}) + (a_{k - 1} \times 10^{k - 1}) + \dots + (a_{1} \times 10^{1}) + (a_{0} \times 10^{0}) .

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

🔗

(a)

$[n] = [a_{0}],$ using congruence classes modulo 5.

🔗

(b)

$n \equiv a_{0} (\mod 5) .$

🔗

(c)

$5 ∣ n$ if and only if $5 ∣ a_{0} .$

🔗

11.

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

🔗

12.

Let $n \in N$ and assume

n = (a_{k} \times 10^{k}) + (a_{k - 1} \times 10^{k - 1}) + \dots + (a_{1} \times 10^{1}) + (a_{0} \times 10^{0}) .

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

🔗

(a)

$[n] = [10 a_{1} + a_{0}],$ using congruence classes modulo 4.

🔗

(b)

$n \equiv (10 a_{1} + a_{0}) (\mod 4) .$

🔗

(c)

$4 ∣ n$ if and only if $4 ∣ (10 a_{1} + a_{0}) .$

🔗

13.

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

🔗

14.

Let $n \in N$ and assume

n = (a_{k} \times 10^{k}) + (a_{k - 1} \times 10^{k - 1}) + \dots + (a_{1} \times 10^{1}) + (a_{0} \times 10^{0}) .

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} (\mod 11) .$ Hence, for congruence classes modulo 11, if $n$ is a nonnegative integer, then $[10^{n}] = [{(- 1)}^{n}] .$

🔗

16.

Let $n \in N$ and assume

n = (a_{k} \times 10^{k}) + (a_{k - 1} \times 10^{k - 1}) + \dots + (a_{1} \times 10^{1}) + (a_{0} \times 10^{0}) .

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

🔗

(a)

$n \equiv \sum_{j = 0}^{k} {(- 1)}^{j} a_{j} (\mod 11) .$

🔗

(b)

$[n] = [\sum_{j = 0}^{k} {(- 1)}^{j} a_{j}],$ using congruence classes modulo 11.

🔗

(c)

$11$ divides $n$ if and only if $11$ divides $\sum_{j = 0}^{k} {(- 1)}^{j} a_{j} .$

🔗

17.

Prove the following propositions.

🔗

(a)

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

Answer.

Prove the contrapositive by calculating $[a]^{2} + [b]^{2}$ for all nonzero $[a]$ and $[b]$ in $Z_{3} .$

🔗

(b)

Let $a, b \in Z .$ If $(a^{2} + b^{2}) \equiv 0 (\mod 3),$ then $a \equiv 0 (\mod 3)$ and $b \equiv 0 (\mod 3) .$

(Use Task 17.a.)

🔗

(c)

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

(Use Task 17.b.)

🔗

18.

Prove the following proposition:

For each $a \in 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 Z .$ If $n$ is odd, then $8 ∣ (n^{2} - 1) .$

Hint.

What are the possible values of $n$ (mod 8)?

🔗

20.

Prove the following proposition:

Let $n \in N .$ If $n \equiv 7 (\mod 8),$ 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} .$

🔗

Activity 46. Using Congruence Modulo 4.

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

🔗

(a)

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

🔗

(b)

Translate the equations $[n^{2}] = [0]$ and $[n^{2}] = [1]$ in $Z_{4}$ into congruences modulo 4.

🔗

(c)

Use a result in Exercise 12 to determine the value of $r$ so that $r \in Z,$ $0 \leq r < 3,$ and

104 257 833 259 \equiv r (\mod 4) .

That is, $[104 257 833 259] = [r]$ in $Z_{4} .$

🔗

(d)

Is the natural number $104 257 833 259$ a perfect square? Justify your conclusion.

Section 7.4 Modular Arithmetic

Beginning Activity Beginning Activity 1: Congruence Modulo 6 A4US

1.

2.

3.

4.

Beginning Activity Beginning Activity 2: The Remainder When Dividing by 9 A4US

1.

2.

3.

4.

5.

6.

Subsection The Integers Modulo n

Definition.

Theorem 3.34 Restated.

Corollary 7.24.

Definition.

Progress Check 7.25. Modular Arithmetic in ,Z2, ,Z5, and Z6.

(a)

(b)

(c)

(d)

(e)

(i)

(ii)

Subsection Divisibility Tests

Proposition 7.26.

Theorem 7.27.

Exercises Exercises

1.

(a)

(b)

(c)

2.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

3.

(a)

(b)

4.

(a)

(b)

5.

(a)

(b)

6.

7.

8.

(a)

(b)

(c)

9.

10.

(a)

(b)

(c)

11.

12.

(a)

(b)

(c)

13.

14.

15.

16.

(a)

(b)

(c)

17.

(a)

(b)

(c)

18.

Beginning Activity Beginning Activity 1: Congruence Modulo 6
A4 US

Beginning Activity Beginning Activity 2: The Remainder When Dividing by 9
A4 US

Subsection The Integers Modulo $n$

Progress Check 7.25. Modular Arithmetic in $Z_{2},$ $Z_{5},$ and $Z_{6}$ .