2.5: Modular Arithmetic
- Page ID
- 99060
We define an equivalence relation that will help us derive insights in number theory. DEFINITION. Divides, \(a \mid b\) Let \(a\) and \(b\) be integers. Then \(a\) divides \(b\), written \(a \mid b\), if there is \(c \in \mathbb{Z}\) such that \[a \cdot c=b .\] DEFINITION. Congruence, \(x \equiv y \bmod n, \equiv_{n}\) Let \(x, y, n \in \mathbb{Z}\) and \(n>1\). Then \[x \equiv y \bmod n\] (or \(x \equiv_{n} y\) ) if \[n \mid(x-y) .\] The relation \(\equiv_{n}\) on \(\mathbb{Z}\) is called congruence \(\bmod n\).
Congruence mod \(n\) is an equivalence relation on \(\mathbb{Z}\).
Prove Theorem 2.25.
The equivalence classes of the relation \(\equiv_{n}\) are called congruence classes, residue classes, or remainder classes \(\bmod n\). The set of congruence classes \(\bmod n\) can be written \(\mathbb{Z}_{n}\) or \(\mathbb{Z} / n \mathbb{Z}\).
Of course \(\mathbb{Z}_{n}\) is a partition of \(\mathbb{Z}\). When \(n=2\), the residue classes are called the even and the odd numbers. Many of the facts you know about even and odd numbers generalize if you think of them as residue classes. What are the residue classes for \(n=3\) ?
We leave it as an exercise (Exercise 2.6) to prove that two integers are in the same remainder class \(\bmod n\) provided that they have the same remainder when divided by \(n\).
Notation. [a] Fix a natural number \(n \geq 2\). Let a be in \(\mathbb{Z}\). We represent the equivalence class of a with respect to the relation \(\equiv_{n}\) by \([a]\).
Proposition 2.26. If \(a \equiv r \bmod n\) and \(b \equiv s \bmod n\), then \[\text { (i) } \quad a+b \equiv r+s \bmod n\] and \[\text { (ii) } a b \equiv r s \quad \bmod n .\] Proof. (i) Assume that \(a \equiv r \bmod n\) and \(b \equiv s \bmod n\). Then \(n \mid(a-r)\) and \(n \mid(b-s)\). So \[n \mid(a+b-(r+s))\] Therefore \[a+b \equiv r+s \quad \bmod n\] proving (i).
To prove (ii), note that there are \(i, j \in \mathbb{Z}\) such that \[a=n i+r\] and \[b=n j+s\] Then \[a b=n^{2} j i+r n j+s n i+r s=n(n j i+r j+s i)+r s\] Therefore \[n \mid(a b-r s)\] and \[a b \equiv r s \quad \bmod n\] Hence the algebraic operations that \(\mathbb{Z}_{n}\) "inherits" from \(\mathbb{Z}\) are welldefined. That is, we may define \(+\) and \(\cdot\) on \(\mathbb{Z}_{n}\) by \[[a]+[b]=[a+b]\] and \[[a] \cdot[b]=[a \cdot b]\] In mathematics, when you ask whether something is "well-defined", you mean that somewhere in the definition a choice was made, and you want to know whether a different choice would have resulted in the same final result. For example, let \(X_{1}=\{-2,2\}\) and let \(X_{2}=\{-1,2\}\). Define \(y_{1}\) by: "Choose \(x\) in \(X_{1}\) and let \(y_{1}=x^{2}\)." Define \(y_{2}\) by: "Choose \(x\) in \(X_{2}\) and let \(y_{2}=x^{2}\)." Then \(y_{1}\) is well-defined, and is the number 4 ; but \(y_{2}\) is not well-defined, as different choices of \(x\) give rise to different numbers.
In (2.27) and (2.28), the right-hand sides depend a priori on a particular choice of elements from the equivalence classes \([a]\) and \([b]\). But Proposition \(2.26\) ensures that sum and product so defined are independent of the choice of representatives of the equivalence classes.
In \(Z_{2}\) addition and multiplication are defined as follows:
(1) \([0]+[0]=[0]\)
(2) \([0]+[1]=[1]+[0]=[1]\)
(3) \([1]+[1]=[0]\)
(4) \([0] \cdot[0]=[0] \cdot[1]=[1] \cdot[0]=[0]\)
(5) \([1] \cdot[1]=[1]\).
Notice that if you read \([0]\) as "even" and [1] as "odd", these are rules that you learned a long time ago.
When working with modular arithmetic we may pick the representatives of remainder classes which best suit our needs. For instance, \[79 \cdot 23 \equiv 2 \cdot 2 \equiv 4 \bmod 7 .\] In other words \[[79 \cdot 23]=[79] \cdot[23]=[2] \cdot[2]=[4] .\] ExAMPLE 2.30. You may recall from your early exposure to multiplication tables that multiplication by nine resulted in a product whose digits summed to nine. This generalizes nicely with modular arithmetic. Specifically, if \(a_{n} \in\ulcorner 10\urcorner\) for \(0 \leq n \leq N\) then \[\sum_{n=0}^{N} a_{n} 10^{n} \equiv \sum_{n=0}^{N} a_{n} \bmod 9 .\] The remainder of any integer divided by 9 equals the remainder of the sum of the digits of that integer when divided by 9 . Proof. The key observation is that \[10 \equiv 1 \bmod 9 .\] Therefore \[\begin{array}{lll} 10^{2} \equiv 1 \cdot 1 \equiv 1 & \bmod 9 \\ 10^{3} \equiv 1 \cdot 1 \cdot 1 \equiv 1 & \bmod 9, \end{array}\] and so on for any power of 10 : \[10^{n} \equiv 1 \bmod 9 \text { for all } n \in \mathbb{N} \text {. }\] (This induction to all powers of 10 is straightforward, but to prove it formally we shall need the notion of mathematical induction from Chapter 4). Therefore on the left-hand side of (2.31), working mod 9, we can replace all the powers of 10 by 1 , and this gives us the right-hand side.
The observation that a number’s residue mod 9 is the same as that of the sum of the digits can be used in a technique called "casting out nines" to check arithmetic.
For example, consider the following (incorrect) sum. The number in the penultimate column is the sum of the digits, and the number in the last column is the repeated sum of the digits until reaching a number between 0 and 9 .
1588 22 4
+1805 14 5
3493 19 1
If the addition had been correctly performed, the remainder mod 9 of the sum would equal the sum of the remainders; so we know a mistake was made.
What is the last digit of \(7^{7}\) ?
We want to know \(7^{7} \bmod 10\). Note that, modulo \(10,7^{0} \equiv 1,7^{1} \equiv\) \(7,7^{2} \equiv 9,7^{3} \equiv 3,7^{4} \equiv 1\). So \(7^{7}=7^{4} 7^{3} \equiv 1 \cdot 3 \equiv 3\), and so 3 is the last digit of \(7^{7}\). EXAMPLE 2.34. What is the last digit of \(7^{7^{7}}\) ?
By Example 2.33, we see that the residues of \(7^{n} \bmod 10\) repeat themselves every time \(n\) increases by 4 . Therefore if \(m \equiv n \bmod 4\), then \(7^{m} \equiv 7^{n} \bmod 10\).
What is \(7^{7} \bmod 4\) ? Well \(7^{1} \equiv 3 \bmod 4,7^{2} \equiv 1 \bmod 4\), so \(7^{7} \equiv\) \(\left(7^{2}\right)^{3} \cdot 7 \equiv 3 \bmod 4\). Therefore \[7^{7^{7}} \equiv 7^{3} \equiv 3 \quad \bmod 10 .\]