True or false: \(19\equiv 5 \mod 2\text{.}\)
Answer 1.
True
True or false: \(19\equiv 5 \mod 7\text{.}\)
Answer 2.
True
True or false: \(19\equiv 5 \mod 5\text{.}\)
Answer 3.
False
Section 8.4 Modular Arithmetic
In the last section we saw that congruence mod \(n\) is an equivalence relation. In this section we will explore this relation in more detail. We will also introduce the concept of modular arithmetic.
Recall the definition for congruence mod \(n\text{,}\) Definition 8.3.2:
Let \(a, b, n\in \mathbb{Z}, n>1\text{.}\) Then \(a\equiv b\mod n\) if \(n\mid (a-b)\text{.}\)
Note, we can use \(n>1\text{,}\) since \(n=1\text{,}\) though defined, is not very interesting since 1 divides everything.
In some applications, and often in computer science, the remainder, \(r\text{,}\) when \(a\) is divided by \(n\) is denoted \(r=a \mod n\text{.}\) When using equals (=), we will mean the specific remainder. When using congruence (\(\equiv\)), we will mean the relation. For example, \(2=12 \mod 5\text{,}\) but many numbers can satisfy the congruence: \(17 \equiv 12 \mod 5\text{,}\) etc.
Example 8.4.1. Congruence mod \(n\).
Activity 8.4.1.
Determine if the following congruences are true or false.
(a)
\(12\equiv 0 \mod 6\)
(b)
\(0\equiv 12 \mod 6\)
(c)
\(12\equiv 5 \mod 7\)
(d)
\(-5\equiv 5 \mod 6\)
(e)
\(-1\equiv 7 \mod 8\)
We use modular arithmetic and equivalence mod \(n\) when we want to think about remainders when dividing by \(n\text{.}\) A familiar example is clock time. Suppose it is 11 am and you have an appointment in 3 hours. In general, you would not think of your appointment for 14 o’clock. You would think of noon as 0, and get that your appointment is at 2 o’clock. There are many more applications in algebra, cryptography, and computer science where we want to classify integers by their remainders mod \(n\text{.}\)
The following theorem will be useful in proving statements involving congruence, but also in helping do calculations.
Theorem 8.4.2.
Let \(a, b, n\in \mathbb{Z}, n>1\text{.}\) The following statements are equivalent.
- \(n\mid a-b\text{;}\)
- \(a\equiv b \mod n\text{;}\)
- \(a=b+kn\) for some \(k\in \mathbb{Z}\text{;}\)
- \(a\) and \(b\) have the same remainder when divided by \(n\text{;}\)
- \(a \mod n = b \mod n\text{,}\) where here we refer to the remainder when dividing by \(n\text{.}\)
Proof.
When proving several statements are equivalent, we need to be able to get from any one statement to any other.
\((1)\Leftrightarrow (2)\) by definition of congruence.
\((4)\Leftrightarrow (5)\) by definition of mod as the remainder.
We will prove \((3)\Leftrightarrow (4)\text{.}\)
Assume \(a=b+kn\) for some \(k\in \mathbb{Z}\text{.}\) By the Quotient-Remainder Theorem, \(a=qn+r\) with \(0\leq r< n\text{.}\) Thus, \(b+kn=qn+r\text{.}\) Solving for \(b\text{,}\) we get \(b=(q-k)n+r\text{.}\) But by uniqueness of the remainder, \(b\) has remainder \(r\text{.}\)
Now assume \(a\) and \(b\) have the same remainder when divided by \(n\text{.}\) By the Quotient-Remainder Theorem, \(a=qn+r\) and \(b=q'n+r\text{.}\) Substituting in for \(r\text{,}\) \(a=qn+b-q'n=b+(q-q')n\text{.}\) Since \((q-q')\in \mathbb{Z}\text{,}\) let \(k=q-q'\text{.}\)
Activity 8.4.2.
Prove part (1) of Theorem 8.4.2 implies part (3).
Activity 8.4.3.
Prove part (3) of Theorem 8.4.2 implies part (1).
The residue of \(a\) modulo \(n\) is the remainder when \(a\) is divided by \(n\text{.}\) The set \(\{0, 1, \ldots, n-1\}\) forms a complete set of residues mod \(n\).
Although we have seen congruence mod \(n\) is an equivalence relation, we formally state it in the following theorem.
Theorem 8.4.3.
Congruence mod \(n\) is an equivalence relation on \(\mathbb{Z}\) with equivalence classes \([0], [1], \ldots [n-1]\text{.}\) Furthermore, \([a]=\{m\in \mathbb{Z} : m=a+kn, k\in \mathbb{Z}\}\text{.}\)
For the proof, see Exercise 8.3.9.
Activity 8.4.4.
Find the equivalence classes for congruence mod 5. List several elements of each equivalence class. What do the elements of each congruence class look like?
Hint.
Think about remainders.
Modular arithmetic is just the process of adding, subtracting, and multiplying, where we treat integers with the same remainder mod \(n\text{,}\) as equivalent. Thus, we can replace any integer with it’s remainder.
Properties of Modular Arithmetic.
If \(a\equiv c \mod n\) and \(b\equiv d \mod n\text{,}\) then
- \(\displaystyle a+b\equiv c+d \mod n\)
- \(\displaystyle a-b\equiv c-d \mod n\)
- \(\displaystyle ab\equiv cd \mod n\)
- \(a^m\equiv c^m \mod n\text{,}\) for \(m\in\mathbb{Z}^+\)
Basically, we can do regular arithmetic, where we can reduce to remainders, or equivalence classes mod \(n\text{.}\)
Example 8.4.4. Modular Arithmetic.
Use modular arithmetic to find
\(10+25 \mod 6\text{.}\)
Answer 1.
\(10\equiv 4 \mod 6, 25\equiv 1\mod 6\text{,}\) so \(10+25\equiv 4+1\equiv 5 \mod 6\)
\(10\cdot 25 \mod 6\text{.}\)
Answer 2.
\(10\cdot 25\equiv 4\cdot 1\equiv 4 \mod 6\)
\(25^{15} \mod 6\text{.}\)
Answer 3.
\(25\equiv 1\mod 6\text{,}\) so \(25^{15}\equiv 1^{15}\equiv 1 \mod 6\)
Activity 8.4.5.
Find \((31+92) \mod 5\) by first reducing 31 and 92 mod 5, then adding.
Activity 8.4.6.
Find \((56)^{21} \mod 5\) by first reducing 56 mod 5, then raising to 21.
Activity 8.4.7.
We can write integers using their decimal expansion. For example, we can write 592 as a decimal expansion: \((5\times 100)+(9\times 10)+2=5\times 10^2+9\times 10^1+2\times 10^0\text{.}\)
(a)
Write 1526 as a similar expansion using powers of 10.
(b)
Find 10 mod 9 and \(10^n\) mod 9 for any \(n\in \mathbb{Z}, n\geq 0\text{.}\)
(c)
Use the decimal expansion and (b) find (592 mod 9) and (1526 mod 9).
If we are doing modular arithmetic we often work directly with the equivalence classes, rather than all of the integers.
We define \(\mathbb{Z}_n=\{0, 1, \ldots, n-1\}\text{,}\) where \(k\in\mathbb{Z}_n\) represents the equivalence class \([k]\text{.}\) Although this sounds complicated, we just do regular arithmetic with \(1, \ldots, n-1\) and reduce to the remainder mod \(n\text{.}\)
Reading Questions Check Your Understanding
1.
True.
False.
True or false: \(47\equiv 2\mod 5\text{.}\)
2.
True.
False.
True or false: \(45\equiv 0\mod 5\text{.}\)
3.
True.
False.
True or false: \(4\equiv -1\mod 5\text{.}\)
4.
True.
False.
True or false: \(14\equiv 1\mod 5\text{.}\)
5.
True.
False.
True or false: \(47+45\equiv 2\mod 5\text{.}\)
6.
True.
False.
True or false: \((47)^2\equiv 4\mod 5\text{.}\)
7.
True.
False.
True or false: \(4^{500}\equiv 1\mod 5\text{.}\)
8.
True.
False.
True or false: \(10\equiv 1\mod 9\text{.}\)
9.
True.
False.
True or false: \(10^2\equiv 1\mod 9\text{.}\)
10.
True.
False.
True or false: \(10^5\equiv 1\mod 9\text{.}\)
11.
True.
False.
True or false: \(10^n\equiv 1\mod 9\text{.}\)
12.
Give the equivalence classes for \(a\equiv b \mod 5\text{.}\)
Hint.
There should be 5 equivalence classes. You only need to give a representative for each class in the form \([a]\text{.}\)
Exercises Exercises
1.
Let \(a=25\) and \(b=19\text{.}\)
- Use the definition of congruence modulo 3 to explain why \(25\equiv 19 \mod 3\text{.}\)
- What value of \(k\) has the property that \(25=19+3k\text{?}\)
- What is the (nonnegative) remainder obtained when 25 is divided by 3? When 19 is divided by 3?
2.
Determine if the following are true or false.
- \(58\equiv 14\) mod \(11\text{.}\)
- \(46\equiv 89\) mod \(13\text{.}\)
- \(674\equiv 558\) mod \(56\text{.}\)
- \(432\equiv 981\) mod \(9\text{.}\)
3.
Verify the following statements by simplifying each expression and using the definition of congruence mod 7.
- \(128\equiv 2 \mod 7\) and \(61\equiv 5 \mod 7\)
- \(\displaystyle (128+61)\equiv (2+5) \mod 7\)
- \(\displaystyle (128-61)\equiv (2-5) \mod 7\)
- \(\displaystyle (128\cdot 61)\equiv (2\cdot 5) \mod 7\)
- \(\displaystyle 128^2\equiv 2^2 \mod 7\)
4.
Prove the transitivity of modular congruence. That is, prove for all \(a, b, c, n\in \mathbb{Z}\) with \(n>1\text{,}\) if \(a\equiv b \mod n\) and \(b\equiv c \mod n\text{,}\) then \(a\equiv c \mod n\text{.}\)
5.
Prove for all \(a, c, n\in \mathbb{Z}\) with \(n>1\text{,}\) if \(a\equiv c \mod n\text{,}\) then \(a^2\equiv c^2 \mod n\text{.}\)
6.
Prove for all \(a, c, n, m\in \mathbb{Z}\) with \(n>1\text{,}\) and \(m\geq 1\text{,}\) if \(a\equiv c \mod n\text{,}\) then \(a^m\equiv c^m \mod n\text{.}\)
Hint.
Use mathematical induction on \(m\text{.}\)
7.
Prove for all integers \(n\geq 0\text{,}\) \(10^n\equiv 1 \mod 9\text{.}\)
8.
Prove that a positive integer, \(N\) is divisible by 9 if and only if the sum of the digits of \(N\) is divisible by 9.
Hint.
The previous problem will be helpful, as will writing \(N\) as a decimal expansion (see Activity 8.4.7). It can be useful in proving that a number is divisible by 9 to instead show that it is congruent to 0 mod 9. Also note, this is an “if and only if” statement so your proof requires two parts.
You have attempted of activities on this page.
