7.4: Modular Arithmetic
- Last updated
- Sep 29, 2021
- Save as PDF
- Page ID
- 86140
( \newcommand{\kernel}{\mathrm{null}\,}\)
PREVIEW ACTIVITY7.4.1: Congruence Modulo 6
For this preview activity, we will only use the relation of congruence modulo 6 on the set of integers.
- Find five different integers a such that a≡3 (mod 6) and find five different integers b such that b≡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.
- 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 0≤r<6 and s≡r (mod 6). What do you observe?
- Calculate p=a⋅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 0≤r<6 and p≡r (mod 6). What do you observe?
- Calculate q=a2 using several values of a in [3] from Part (1). For each product q that is calculated, find r so that 0≤r<6 and q≡r (mod 6). What do you observe?
PREVIEW ACTIVITY 7.4.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
a=bq+r and 0≤r<b.
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 int(x) is the greatest integer that is less than or equal to x.]
So, in the context of the Division Algorithm, q=int(ab). Consequently,
r=a−b⋅int(ab).
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.
- n=498
- n=7319
- n=4672
- n=9845
- n=51381
- n=305877
What do you observe?
The Integers Modulo n
Let n∈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: integers modulo n
Let n∈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 Zn.
Corollary 7.17 tells us that
Z=[0]∪[1]∪[2]∪⋅⋅⋅∪[n−1].
In addition, we know that each integer is congruent to precisely one of the integers 0, 1, 2, ..., n−1. This tells us that one way to represent Zn is
Zn={[0],[1],[2],...[n−1]}.
Consequently, even though each integer has a congruence class, the set Zn 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 Zn. For example, in the integers modulo 5, Z5, is it possible to add the congruence classes [4] and [2] as follows?
[4]⊕[2]=[4+2]=[6]=[1].
We have used the symbol ̊ to denote addition in Z5 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,
9≡4 (mod 5) and so [9] = [4]. Also,
7≡2 (mod 5) and so [7] = [2].
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]⊕[7]=[9+7]=[16]=[1].
This is one of the ideas that was explored in Preview Activity 7.4.1. The main difference is that in this preview activity, we used the relation of congruence, and here we are using congruence classes. All of the examples in Preview Activity 7.4.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≡3 (mod 6) and b≡4 (mod 6), then
|
If [a]=[3] and [b]=[4] in Z6, then
|
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 Zn.
Theorem 3.28
Let n be a natural number and let a, b, c, and d be integers. Then
- If a≡b (mod n) and c≡d (mod n), then (a+c)≡(b+d) (mod n).
- If a≡b (mod n) and c≡d (mod n), then ac≡bd (mod n).
- If a≡b (mod n) and m∈N, then am≡bm (mod n).
- Proof
-
Add proof here and it will automatically be hidden
Since x≡y (mod n) if and only if [x]=[y], we can restate the result of this Theorem 3.28 in terms of congruence classes in Zn.
Corollary 7.19.
Let n be a natural number and let a, b, c, and d be integers. Then, in Zn.
- If [a]=[b] and [c]=[d], then [a+c]=[b+d].
- If [a]=[b] and [c]=[d], then [a⋅c]=[b⋅d].
- If [a]=[b] and m∈N, then [a]m=[b]m.
Because of Corollary 7.19, we know that the following formal definition of addition and multiplication of congruence classes in Zn 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∈N. Addition and multiplication in Zn are defined as follows: For [a],[c]∈Zn,
[a]⊕[c]=[a+c] and [a]⊙[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∈N, then we have an addition and multiplication defined on Zn, the integers modulo n.
Always remember that for each of the equations in the definitions, the operations on the left, ⊕ and ⊙, are the new operations that are being defined. The operations on the right side of the equations (+ and ⋅) are the known operations of addition and multiplication in Z.
Since Zn is a finite set, it is possible to construct addition and multiplication tables for Zn. In constructing these tables, we follow the convention that all sums and products should be in the form [r], where 0≤r<n. For example, in Z3, we see that by the definition, [1]⊕[2]=[3], but since 3≡0 (mod 3), we see that [3]=[0] and so we write
[1]⊕[2]=[3]=[0]
Similarly, by definition, [2]⊙[2]=[4], and in Z3, [4] = [1]. So we write
[2]⊙[2]=[4]=[1]
The complete addition and multiplication tables for Z3 are
Progress Check 7.20 (Modular Arithmetic in Z2, Z5, and Z6)
- Construct addition and multiplication tables for Z2, the integers modulo 2.
- Verify that the following addition and multiplication tables for Z5 are correct.
- Construct complete addition and multiplication tables for Z6.
- In the integers, the following statement is true. We sometimes call this the zero product property for the integers.
For all a,b∈Z, if a⋅b=0, then a=0 or b=0.
Write the contrapositive of the conditional statement in this property. - Are the following statements true or false? Justify your conclusions.
(a) For all [a],[b]∈Z5, if [a]⊙[b]=[0], then [a]=[0] or [b]=[0].
(b) For all [a],[b]∈Z6, if [a]⊙[b]=[0], then [a]=[0] or [b]=[0].
- Answer
-
Add texts here. Do not delete this text first.
Divisibility Tests
Congruence arithmetic can be used to proof 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∈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 Preview Activity 7.4.2, we saw that
7319≡2 (mod 9) and 20≡2 (mod 9).
In fact, for every example in Preview Activity 7.4.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=(7×103)+(3×102)+(1×101)+(9×100).
The idea is to now use the definition of addition and multiplication in Z9 to convert equation (7.4.3) to an equation in Z9. We do this as follows:
[7319]=[(7×103)+(3×102)+(1×101)+(9×100)]=[7×103]⊕[3×102]⊕[1×101]⊕[9×100]=([7]⊙[103])⊕([3]⊙[102])⊕([1]⊙[101])⊕([9]⊙[1]).
Since 103≡1 (mod 9), 102≡1 (mod 9) and 10≡1 (mod 9), we can conclude that [103]=[1], [102]=[1] and [10]=[1]. Hence, we can use these facts and equation (7.4.4) to obtain
[7319]=([7]⊙[103])⊕([3]⊙[102])⊕([1]⊙[10])⊕([9]⊙[1])=([7]⊙[1])⊕([3]⊙[1])⊕([1]⊙[1])⊕([9]⊙[1])=[7]⊕[3]⊕[1]⊕[9]=[7+3+1+9].
Equation (7.4.5) 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 (7.4.3).
In general, if n∈N, and n=akak−1⋅⋅⋅a1a0 is the decimal representation of n, then
n=(ak×10k)+(ak−1×10k−1)+⋅⋅⋅+(a1×101)+(a0×100).
This can also be written using summation notation as follows:
n=∑kj=0(aj×10j).
Using congruence classes for congruence modulo 9, we have
[n]=[(ak×10k)+(ak−1×10k−1)+⋅⋅⋅+(a1×101)+(a0×100)]=[ak×10k]⊕[ak−1×10k−1]⊕⋅⋅⋅⊕[a1×101]⊕[a0×100]=([ak]⊙[10k])⊕([ak−1]⊙[10k−1])⊕⋅⋅⋅⊕([a1]⊙[101])⊕([a0]⊙[100]).
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 10n≡1 (mod 9), and hence for the equivalence relation of congruence modulo 9, [10n]=[1].
If we let s(n) denote the sum of the digits of n, then
s(n)=ak+ak−1+⋅⋅⋅+a1+a0.
Now using equation (7.4.6) and Proposition 7.21, we obtain
\[\begin{array} {rcl} {[n]} &= & {([a_k] \odot [1]) \oplus ([a_{k - 1}] \odot [1]) \oplus \cdot\cdot\cdot \oplus ([a_1] \odot [1]) \oplus ([a_0] \odot [1])} \\ {} &= & {[a_k] \oplus [a_{k - 1}] \oplus \cdot\cdot\cdot \oplus [a_1] \oplus [a_0] \\ {} &= & {[a_k + a_{k-1} + \cdot\cdot\cdot + a_1 + a_0].} \\ {} &= & {[s(n)].} \end{array}\]
This completes the proof of Theorem 7.22.
Theorem 7.22.
Let n∈N and let s(n) denote the sum of the digits of n. Then
- [n]=[s(n)], using congruence classes modulo 9.
- n≡s(n) (mod 9)
- 9 | n if and only if 9 | 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.
Exercise 7.4
- (a) Complete the addition and multiplication tables for Z4.
(b) Complete the addition and multiplication tables for Z7.
(c) Complete the addition and multiplication tables for Z8. - The set Zn contains n elements. One way to solve an equation in Zn is to substitute each of these n elements in the equation to check which ones are solutions. In Zn, 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 Z4
(b) [x]2=[1] in Z8
(c) [x]4=[1] in Z5
(d) [x]2⊕[3]⊙[x]=[3] in Z6
(e) [x]2⊕[1]=[0] in Z5
(f) [3]⊙[x]⊕[2]=[0] in Z5
(g) [3]⊙[x]⊕[2]=[0] in Z6
(h) [3]⊙[x]⊕[2]=[0] in Z9 - In each case, determine if the statement is true or false.
(a) For all [a]∈Z6, if [a]≠[0], then there exists a [b]∈Z6 such that [a]⊙[b]=[1].
(b) For all [a]∈Z5, if [a]≠[0], then there exists a [b]∈Z5 such that [a]⊙[b]=[1]. - In each case, determine if the statement is true or false.
(a) For all [a],[b]∈Z6, if [a]≠[0] and [b]≠[0], then [a]⊙[b]≠[0].
(b) For all [a],[b]∈Z5, if [a]≠[0] and [b]≠[0], then [a]⊙[b]≠[0]. - (a) Prove the following proposition:
For each [a]∈Z5, if [a]≠[0], then [a]2=[1] or [a]2=[4].
(b) Does there exist an integer a such that a2=5,158,232,468,953,153? Use your work in Part (a) to justify your conclusion. Compare to Exercise (10) in Section 3.5. - Use mathematical induction to prove Proposition 7.21.
If n is a nonnegative integer, then 10n≡1 (mod 9), and hence for the equivalence relation of congruence modulo 9, [10n]=[1]. - Use mathematical induction to prove that if n is a nonnegative integer, then 10n≡1 (mod 3). Hence, for congruence classes modulo 3, if n is a nonnegative integer, then [10n]=[1].
- Let n∈N and let s(n) denote the sum of the digits of n.So if we write
n=(ak×10k\)+(ak−1×10k−1+⋅⋅⋅+(a1×101)+(a0×100).
then s(n)=ak+ak−1+⋅⋅⋅+a1+a0. Use the result in Exercise (7) to help prove each of the following:
(a) [n]=[s(n)], using congruence classes modulo 3.
(b) n≡s(n) (mod 3).
(c) 3 | n if only if 3 | s(n). - Use mathematical induction to prove that if n is an integer and nge1, then 10n≡0 (mod 5). Hence, for congruence classes modulo 5, if n is an integer and n≥1, then [10n]=[0].
- Let n∈N and assume
n=(ak×10k)+(ak−1×10k−1+⋅⋅⋅+(a1×101)+(a0×100).
Use the result in Exercise (9) to help prove each of the following:
(a) [n]=[a0], using congruence classes modulo 5.
(b) n≡a0 (mod 5).
(c) 5 | n if only if 5 | a0. - Use mathematical induction to prove that if n is an integer and nge2, then 10n≡0 (mod 4). Hence, for congruence classes modulo 4, if n is an integer and n≥2, then [10n]=[0].
- Let n∈N and assume
n=(ak×10k)+(ak−1×10k−1+⋅⋅⋅+(a1×101)+(a0×100).
Use the result in Exercise (11) to help prove each of the following:
(a) [n]=[10a1+a0], using congruence classes modulo 4.
(b) n≡(10a1+a0) (mod 5).
(c) 4 | n if only if 4 | (10a1+a0). - Use mathematical induction to prove that if n is an integer and nge3, then 10n≡0 (mod 8). Hence, for congruence classes modulo 8, if n is an integer and n≥3, then [10n]=[0].
- Let n∈N and assume
n=(ak×10k)+(ak−1×10k−1+⋅⋅⋅+(a1×101)+(a0×100).
Use the result in Exercise (13) to help develop a divisibility test for 8. Prove that your divisibility test is correct. - Use mathematical induction to prove that if n is a nonnegative integer then 10n≡(−1)n(mod11). Hence, for congruence classes modulo 11, if n is a nonnegative integer, then [10n]=[(−1)n].
- Let n∈N and assume
n=(ak×10k)+(ak−1×10k−1+⋅⋅⋅+(a1×101)+(a0×100).
Use the result in Exercise (15) to help prove each of the following:
(a) n≡∑kj=0(−1)jaj (mod 11).
(b) [n]=[∑kj=0(−1)jaj], using congruence classes modulo 11.
(c) 11 divides n if and only if 11 divides ∑kj=0(−1)jaj - (a) Prove the following proposition:
For all [a],[b]∈Z3, if [a]2+[b]2=[0], then [a]=0 and [b]=[0].
(b) Use Exercise (17a) to prove the following proposition:
Let a,b∈Z. If (a2+b2)≡0 (mod 3), then a≡0 (mod 3) and b≡0 (mod 3).
(c) Use Exercise (17b) to prove the following proposition:
Let a,b∈Z, if 3 divides (a2+b2), then 3 divides a and 3 divides b. - Prove the following proposition:
For each a∈Z, if there exist integers b and c such that a=b4+c4, then the units digit of a must be 0, 1, 2, 5, 6, or 7. - Is the following proposition true or false? Justify your conclusion.
For n∈Z. If n is odd, then 8 | (n2−1). Hint: What are the possible values of n (mod 8)? - Prove the following proposition:
For n∈Z. If n≡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=a2+b2+c2.
Explorations and Activities - Using Congruence Modulo 4. The set Zn is a finite set, and hence one way to prove things about Zn is to simply use the n elements in Zn as the n cases for a proof using cases. For example, if n∈Z, then in Z4, [n]=[0], [n]=[1], [n]=[2], or [n]=[3].
(a) Prove that if n∈Z, then in Z4, [n]2=[0] or [n]2=[1]. Use this to conclude that in Z4, [n2]=[0] or [n2]=[1].
(b) Translate the equations [n2]=[0] and [n2]=[1] in Z4 into congruences modulo 4.
(c) Use a result in Exercise (12) to determine the value of r so that r∈Z, 0≤r<3, and
104 257 833 259≡r (mod 4).
That is, [104 257 833 259]=[r] in Z4.
(d) Is the natural number 104 257 833 259 a perfect square? Justify your conclusion.
- Answer
-
Add texts here. Do not delete this text first.