5.4 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\).
Linear congruences.
We now return to the question of cancellation of congruence classes, postponed from earlier in this chapter.
We would like to be able to simplify an expression of the form \([a][b]=[a][c]\) in order to conclude that \([b]=[c]\).
However this is not always true:
Let \(a=2, b=3, c=0\) and \(n=6\). Then \([a][b]=[6]=[0]=[a][c]\), however \([b]=[3]\ne[0]=[c]\). This is reminiscent of the fact that we cannot always cancel even when dealing with integers, since we cannot cancel 0. In the case of mod \(6\) arithmetic we cannot cancel \([2]\) either.
Cancellation
However we can sometimes cancel, so for example, if \([5][b]=[5][c]\) mod \(6\), then \([b]=[c]\). To prove this notice that if \([5][b]=[5][c]\), then \([5][5][b]=[5][5][c]\), so \([25][b]=[25][c]\). But \([25]=[1]\) mod \(6\), so \([b]=[c]\).
More generally if we can find a congruence class \([a']\) such that \([a'][a]=[1]\) then we can cancel \([a]\) by multiplying by \([a']\).
Another way to think of this
If \(b\) is an integer divisible by an integer \(a\), then \(b=aq\) for some integer \(q\), which we called the quotient of \(b\) by \(a\). To say that a congruence class \([b]\) is divisible by another congruence class \([a]\) is to say that there is a congruence class \([q]\) such that \([b]=[a][q]\).
Finding divisors
In order to decide whether or not \([b]\) is divisible by \([a]\) we need to consider the solutions of the linear congruence \(ax\equiv b\text{ mod }(n)\).
Note that if \(x\) is a solution, and if \(x'\equiv x\), then \(ax'\equiv ax\equiv b\) and so \(x'\) is also a solution; thus the solutions (if they exist) form a union of congruence classes.
Now \(ax\equiv b\text{ mod }(n)\) if and only if \(ax-b\) is a multiple of \(n\), so \(x\) is a solution of this linear congruence if and only if there is integer \(y\) such that \(x\) and \(y\) satisfy the linear diophantine equation \(ax+ny=b\), which we studied (with slightly different notation) in Chapter 3. Translating Theorem 3.31 into the language of congruences we have:
If \(d=\gcd(a,n)\), then the linear congruence \[ax\equiv b\text{ mod }(n)\] has a solution if and only if \(d\) divides \(b\).
If \(d\) does divide \(b\), and if \(x_0\) is any solution, then the general solution is given by \[x=x_0+ct\] where \(n=cd\), and \(t\in{\mathbb Z}\).
In particular, the solutions form exactly \(d\) congruence classes \(\text{mod }(n)\), with representatives \[x=x_0,\; x_0+{c},\; x_0+{2c},\; \ldots,\; x_0+{(d-1)c}\,.\]
Proof. Apart from a slight change of notation, the only part of this which is not a direct translation of Theorem 3.31 is the statement about congruence classes. To prove this, note that \[x_0+{tc}\equiv x_0+{t'c}\text{ mod }(n)\] if and only if \(n\) divides \((t-t')c\), that is, if and only if \(d\) divides \(t-t'\), so the congruence classes of solutions \(\text{mod }(n)\) are obtained by letting \(t\) range over a complete set of residues \(\text{mod }(d)\), such as \(0, 1, \ldots, d-1\).
Solve the congruence \[10x\equiv 3\text{ mod }(12)\,.\]
Here \(a=10\), \(b=3\) and \(n=12\), so \(d=\gcd(10,12)=2\); this does not divide \(3\), so there are no solutions. (This can be seen directly: the elements of the congruence class \([3]\) in \({\mathbb Z}_{12}\) are all odd, whereas any elements of \([10][x]\) must be even.)
Solve the congruence \[10x\equiv 6\text{ mod }(12)\,.\]
As before we have \(d=2\), and now this does divide \(b=6\), so there are two classes of solutions. We can take \(x_0=3\) as a particular solution, so the general solution has the form \[x=3+\frac{12t}{2}=3+6t\,,\] where \(t\in{\mathbb Z}\). These solutions form two congruence classes \([3]\) and \([9]\text{ mod }(12)\), with representatives \(x_0=3\) and \(x_0+(n/d)=9\); equivalently, they form a single congruence class \([3]\text{ mod }(6)\).
Find the general solution of the congruence \(12x\equiv 9 \text{ mod }(15)\).
If \(\gcd(a,n)=1\) then the solutions of the linear congruence \(ax\equiv b\text{ mod }(n)\) form a single congruence class \(\text{mod }(n)\).
Proof. Put \(d=1\) in Theorem 5.28.
There are three possibilities:
- If \(a\) and \(n\) are coprime then for each \(b\) there is a unique class \([x]\) such that \([a][x]=[b]\) in \({\mathbb Z}_n\).
- If \(d=\gcd(a,n)>1\) and \(d|b\) then there is more than one such class \([x]\)
- If \(d\nmid b\) there is no such class.
Consider the congruence \[7x\equiv 3\text{ mod }(12)\,.\] Here \(a=7\) and \(n=12\), and since these are coprime there is a single congruence class of solutions; this is the class \([x]=[9]\), since \(7\times 9=63\equiv 3\text{ mod }(12)\).