5.3 Modular Arithmetic
For a given \(n\geq 1\), we denote the set of \(n\) equivalence classes mod \((n)\) by \({\mathbb Z}_n\). This set is known as the set of integers \(\text{mod }(n)\).
Our next aim is to show how to do arithmetic with these congruence classes, so that \({\mathbb Z}_n\) becomes a number system with properties very similar to those of \({\mathbb Z}\).
We define the binary operations of addition, subtraction and multiplication on the congruence classes in \({\mathbb Z}_n\) in terms of the corresponding operations in \({\mathbb Z}\). If \([a]\) and \([b]\) are elements of \({\mathbb Z}_n\), we define their sum, difference and product to be the classes
- \([a]+[b]=[a+b]\)
- \([a][b]=[ab]\)
For example, for \(n=3\), \(\mathbb Z_3=\{[0], [1], [2]\}\)
\[ \begin{array}{c|ccc} +&[0]&[1]&[2]\\\hline [0]&[0]&[1]&[2]\\ {[1]}&[1]&[2]&[0]\\ {[2]}&[2]&[0]&[1]\\ \end{array} \] \[ \begin{array}{c|ccc} \times&[0]&[1]&[2]\\\hline [0]&[0]&[0]&[0]\\ {[1]}&[0]&[1]&[2]\\ {[2]}&[0]&[2]&[1]\\ \end{array} \]
Checking that these operations make sense
Notice that \([2]+[3] = [2]\), that \([5] = [2]\) and \([5]+[3] = [8] = [2]\).
We need to show that these three operations are well-defined, in the sense that the right-hand sides of the three equations defining them depend only on the classes \([a]\) and \([b]\), and not on the particular elements \(a\) and \(b\) we have chosen from those classes.
In other words, we must show that if \([a]=[a']\) and \([b]=[b']\), then \([a+b]=[a'+b'],\;[a-b]=[a'-b']\) and \([ab]=[a'b']\). These follow immediately from Proposition 5.10 and the following result.
For any \(n\geq 1\), if \(a'\equiv a\) and \(b'\equiv b\) then
- \(a'+b'\equiv a+b\)
- \(a'-b'\equiv a-b\) and
- \(a'b'\equiv ab\).
Proof. If \(a'\equiv a\) then \(a'=a+kn\) for some integer \(k\), and similarly we have \(b'=b+ln\) for some integer \(l\); then \(a'+ b'=(a+ b)+(k+l)n\equiv a+b\), \(a'- b'=(a-b)+(k-l)n\equiv a-b\) and \(a'b'=ab+(al+bk+kln)n\equiv ab\).
Show that each of the axioms [A1] - [A6] for the integers, which we listed in Chapter 1, also hold for \(\mathbb Z_n\). Show also that axiom [A7] does not, in general, hold.
What about \([x]^{[y]}\)?
Note that not all arithmetic operations from \(\mathbb Z\) have well-defined counterparts in \(\mathbb Z_n\). For example, let us look at what happens if we try to define exponentiation of classes in \({\mathbb Z}_n\) in the obvious way.
We could define \[[a]^{[b]}=[a^b]\,,\] restricting \(b\) to non-negative values to ensure that \(a^b\) is an integer. Notice that \([a]^{[b]}\) is not the same as \([a]^b\) which is equal to \(\underbrace{[a][a]\ldots[a]}_{\text{b times}}\).
So for \(n=3\), we would have, for example, \[[2]^{[1]}=[2^1]=[2]\,;\]
Exponentiation of congruence classes is not well-defined.
Unfortunately, \([1]=[4]\) in \({\mathbb Z}_3\), and our definition would then mean \[[2]^{[4]}=[2^4]=[16]=[1]\neq [2]=[2]^{[1]}.\] Thus we can get different congruence classes for \([a]^{[b]}\) by choosing different elements \(b\) and \(b'\) in the same class \([b]\). This is because the operation is not well-defined, or in other words, \(a'\equiv a\) and \(b'\equiv b\) do NOT imply \((a')^{b'}\equiv a^b\).
We therefore confine arithmetic in \({\mathbb Z}_n\) to operations which are well-defined, like addition, subtraction, multiplication and integer powers.
We can sometimes cancel or even “divide” in modular arithmetic, but not always so we must be careful.
Let \(n=10\). Then \([7][2]=[14]=[4]\) but also \([2][2]=[4]\) but \([2]\neq [7]\).
So \([7][2]=[2][2]\) but we cannot cancel the factor of \([2]\).
For example for \(n=3\) we saw that \([2][2]=[1]\) so \([2]\) is a unit and is a multiplicative inverse for itself.
Remark / Question: \([n-1]\) is always a unit and is a multiplicative inverse for itself. Why?
When we have a multiplicative inverse then we can cancel a factor.
Let \(n=10\). Then \([3][7]=[21]=[1]\).
So if \([7][a]=[7][b]\) then we can deduce that \([a]=[b]\) because \[[a]=[1][a]=([3][7])[a]=[3]([7][a])=[3]([7][b])=([3][7])[b]=[1][b]=[b].\]
One of the main points of Lemma 5.11 is that we can perform rather complicated calculations involving modular arithmetic, one step at a time.
For example to calculate with the expression \(12^5+89\times(15^6-13^7)\) whilst working modulo \(8\), instead of expanding the expression to find it equals \(-4570603556\) and then trying to calculate which number it is congruence to modulo 8, we can replace different parts of the expression and simplify as we go along.
So \(12\equiv4\text{ mod }8\) and hence \(12^5\equiv 4^5\text{ mod }8\). But \(4^2 = 16\equiv0\text{ mod }8\) and so \(12^5\equiv 4^2\times 4^2\times 4 \equiv 0\times 0\times4 = 0\text{ mod }8\).
In a similar way \(89\equiv1\text{ mod }8\), \(15^6\equiv 1\text{ mod }8\), \(13^7\equiv5\text{ mod }8\) and so \(12^5+89\times(15^6-13^7)\equiv 0+1\times(1-5) = -4\equiv4\text{ mod }8\).
Back to Example 5.1
Every integer is congruence to the sum of its digits modulo 9.
Let \(x=10^nx_n+\ldots +10x_1 + x_0\).
Since \(10\equiv1 (\!\!\!\mod 9)\) then \(10^n\equiv1^n=1 (\!\!\!\mod 9)\) and so \(x\equiv 1\times x_n\ldots+1\times x_1 + x_0 = x_n+\dots +x_0(\!\!\!\mod 9)\).
Residues
A set of \(n\) integers, containing one representative from each of the \(n\) congruence classes in \({\mathbb Z}_n\), is called a complete set of residues \(\text{mod }(n)\). In principle, we can use any complete set of residues but a sensible choice can ease calculations considerably.
The most obvious choice is provided by the Remainder Theorem (Theorem 3.4). We can divide any integer \(a\) by \(n\) to give \(a=qn+r\) for some unique \(r\) satisfying \(0\leq r<n\); thus each class \([a]\in{\mathbb Z}_n\) contains a unique \(r=0, 1, \ldots, n-1\), so these \(n\) integers form a complete set of residues, called the least non-negative residues \(\text{mod }(n)\).
The least absolute residues
For many purposes these are the most convenient residues to use, but sometimes it is better to replace Theorem 3.4 with Exercise 3.5 which gives a remainder \(r\) satisfying \(-n/2<r\leq n/2\).
These remainders are the least absolute residues \(\text{mod }(n)\), those with least absolute value. When \(n\) is odd they are \(0, \pm 1, \pm 2, \ldots, \pm(n-1)/2\), and when \(n\) is even we also have to include \(n/2\). The following calculations illustrate these complete sets of residues.
Let us calculate the least non-negative residue of \(26\times 32\text{ mod }33\).
Using least absolute residues \(\text{mod }(33)\), we have \(26\equiv -7\) and \(32\equiv -1\), so Lemma 5.11 implies that \(26\times 32\equiv (-7)\times(-1)\equiv 7\). Since \(0\leq 7<33\) it follows that \(7\) is the required least non-negative residue.
Calculate the least absolute residue of \(15\times 59\text{ mod }(75)\).
We have \(15\times 59\equiv 15\times(-16)\), and a simple way to evaluate this is to do the multiplication in several stages, reducing the product \(\text{mod }(75)\) each time. Thus \[15\times(-16)=15\times(-4)\times 4=(-60)\times 4\equiv 15\times 4=60\equiv -15\,,\] and since \(-75/2<-15\leq 75/2\) the required residue is \(-15\).
Calculate the least non-negative residue of \(7^8\text{ mod }(17)\).
We do this in several stages, reducing \(\text{mod }(17)\) whenever possible: \[7^2=49\equiv -2\,,\] so that \[7^4=(7^2)^2\equiv(-2)^2=4\,,\] and hence \[7^8=(7^4)^2\equiv 4^2=16\,;\] the required residue is therefore \(16\).
Without using a calculator
- find the least absolute residue of \(31(33+35)\text{ mod }(23)\);
- find the least non-negative residue of \(31^{33}\text{ mod }(29)\);
- explain why the last decimal digit of \(1! + 2! + \ldots + n!\) can only take one of 3 possible values and find those values.
Divisibility and congruences
Since \(n\) divides \(m\) if and only if \(m\equiv 0\text{ mod }(n)\) if and only if \([m]_n=[0]_n\) it follows that problems about divisibility are equivalent to problems about congruences, and these can sometimes be easier to solve. For example
Let us prove that \(a(a+1)(2a+1)\) is divisible by \(6\) for every integer \(a\).
By taking least absolute residues \(\text{mod }(6)\), we see that if \(a\) is any integer, then \(a\equiv 0, \pm 1, \pm 2\) or \(3\). We examine each possibility. If \(a\equiv 0\) then \(a(a+1)(2a+1)\equiv 0\times1\times1\equiv 0\). If \(a\equiv 1\) then \(a(a+1)(2a+1)\equiv 1\times2\times3=6\equiv 0\). Proceeding in this way we can show that \(a(a+1)(2a+1)\equiv 0\) in the other four cases, so \(6|a(a+1)(2a+1)\) for all \(a\).
There is a quicker proof of this, based on the observation that \(6|m\) if and only if \(2|m\) and \(3|m\). We shall make use of this principle later in the course.
Solution. For any \(a\) either \(a\) or \(a+1\) must be even and so congruent to \(0\) mod \(2\) so \(a(a+1)(2a+1)\equiv0\) mod \(2\). By the same principle at least one of the three integers \(a, a+1, 2a+1\) is congruent to \(0\) mod \(3\). To see this note that \(a\) is congruent to \(0,1\) or \(2\) mod \(3\), so we get \(a\equiv0\) mod \(3\), or \(2a+1\equiv0\) mod \(3\), or \(a+1\equiv0\) mod \(3\), respectively. Hence the product \(a(a+1)(2a+1)\equiv0\) mod \(3\), and since \(2\) and \(3\) are coprime, \(a(a+1)(2a+1)\equiv0\) mod \(6\).
The previous argument uses the following more general principle, in which a single congruence \(\text{mod }(n)\) is replaced with a set of simultaneous congruences \(\text{mod }(p^e)\) for the various prime powers \(p^e\) dividing \(n\).
Let \(n\) have prime power factorisation \[n=p_1^{e_1}\cdots p_k^{e_k},\] where \(p_1, \ldots, p_k\) are distinct primes. Then for any integers \(a\) and \(b\) we have \(a\equiv b\text{ mod }(n)\) if and only if \(a\equiv b\text{ mod }(p_i^{e_i})\) for each \(i=1, \ldots, k\).
We shall delay a formal proof of this until we have met the Chinese Remainder Theorem later in this Chapter. However, as an exercise, you may like to prove it directly, using Corollary 3.27.
Polynomials over \(\mathbb Z_n\).
Let \(f(x)\) be a polynomial with integer coefficients, and let \(n\geq 1\). If \(a\equiv b \text{ mod }(n)\) then \(f(a)\equiv f(b)\text{ mod }(n)\).
Proof. Write \(f(x)=c_0+c_1x+\cdots+c_kx^k\), where each \(c_i\in{\mathbb Z}\). If \(a\equiv b\text{ mod }(n)\), then repeated use of Lemma 5.11 implies that \(a^i\equiv b^i\) for all \(i\geq 0\), so \(c_ia^i\equiv c_ib^i\) for all \(i\), and hence \(f(a)=\sum c_ia^i\equiv \sum c_ib^i=f(b)\).
For an illustration of this, look at Example 5.20, where we took \(f(x)=x(x+1)(2x+1)=2x^3+3x^2+x\) and \(n=6\); we then used the fact that if \(a\equiv 0, \pm 1, \pm 2\) or \(3\) then \(f(a)\equiv f(0), f(\pm 1), f(\pm 2)\) or \(f(3)\) respectively, all of which are easily seen to be congruent to \(0\text{ mod }(6)\).
Showing that a polynomial has no integer roots
Suppose that a polynomial \(f(x)\), with integer coefficients, has an integer root \(x=a\in{\mathbb Z}\), so that \(f(a)=0\). It follows then that \(f(a)\equiv 0\text{ mod }(n)\) for all integers \(n\geq 1\). The contrapositive of this says:
if there exists an integer \(n\geq 1\) such that the congruence \(f(x)\equiv 0\text{ mod }(n)\) has no solutions, then the equation \(f(x)=0\) has no integer solutions.
We can often use this to show that certain polynomials \(f(x)\) have no integer roots. If \(n\) is small we can check whether \(f(x)\equiv 0\text{ mod }(n)\) has any solutions simply by evaluating \(f(x_1), \ldots, f(x_n)\) where \(x_1, \ldots, x_n\) form a complete set of residues \(\text{mod }(n)\). Since each \(x\in{\mathbb Z}\) is congruent to some \(x_i\), then Lemma 5.23 implies that \(f(x)\equiv f(x_i)\), and we simply determine whether any of \(f(x_1), \ldots, f(x_n)\) is divisible by \(n\).
Let us prove that the polynomial \(f(x)=x^5-x^2+x-3\) has no integer roots.
To do this, we take \(n=4\) (see later for why we choose \(4\)), and consider the congruence \[f(x)=x^5-x^2+x-3\equiv 0\text{ mod }(4)\,.\] Using the least absolute residues \(0, \pm 1, 2\) as a complete set of residues \(\text{mod }(4)\), we find that \[f(0)=-3,\quad f(1)=-2,\quad f(-1)=-6\quad\text{and}\quad f(2)=27\,.\]
None of these values is divisible by \(4\), so the congruence \(f(x)\equiv 0\text{ mod }(4)\) has no solutions and hence the polynomial \(f(x)\) has no integer roots.
Why choose \(n=4\)?
The reason is quite simple. For each value of \(n<4\) the congruence \(f(x)\equiv 0\text{ mod }(n)\) DOES have a solution \(x\in{\mathbb Z}\), even though the equation \(f(x)=0\) does not. So \(4\) is the smallest value of \(n\) for which this method works. If one value of \(n\) fails to prove that a polynomial has no integer roots just try a few more values, and if they also fail, this suggests that perhaps there really is an integer root.
Prove that the following polynomials have no integer roots:
- \(x^3-x+1\);
- \(x^3+x^2-x+1\);
- \(x^3+x^2-x+3\).
Unfortunately, the method used in Example 5.24 is not always strong enough to prove the non-existence of integer roots. For instance, the polynomial \[f(x)=(x^2-13)(x^2-17)(x^2-221)\] clearly has no integer roots: indeed, since \(13, 17\) and \(221\;(=13\times 17)\) are not perfect squares, the roots \(\pm\sqrt{13}, \pm\sqrt{17}\) and \(\pm\sqrt{221}\) of \(f(x)\) are all irrational by Corollary 4.6. However, it can be shown that for every integer \(n\geq 1\) there is a solution of \(f(x)\equiv 0\text{ mod }(n)\), so in this case there is no suitable choice of \(n\) for our method of congruences.
There is no non-constant polynomial \(f(x)\), with integer coefficients, such that \(f(x)\) is prime for all integers \(x\).