Chapter 4 Congruences
At the time of typsetting these notes, it was 11 o’clock. In 1 hours time it will be 12 o’clock and in 2 hours it will be 13 o’clock. Of course we don’t normally refer to that time as 13 o’clock, but rather as 1 o’clock. In referring to the time, we use a system of arithmetic that we refer to as modular arithmetic. In modular arithmetic we simplify number-theoretic problems by replacing each integer with its remainder when divided by some fixed positive integer \(n\). So, for example, when telling the time we use \(n=12\).
This has the effect of replacing the infinite number system \(\mathbb Z\) with a number system \({\mathbb Z}_n\) which contains a finite number (\(n\)) of elements.
In this and the next chapter we shall study the properties of this new number system and show that we can perform arithmetic on these ‘numbers’ in the same way we can for the integers. We will find that we can
- add,
- subtract and
- multiply
the elements of \({\mathbb Z}_n\), just as we can in \({\mathbb Z}\).
WARNING: as usual we will avoid ‘’division’’ but for modular arithmetic there are even some difficulties with cancellation.
Modular arithmetic
Show that an integer is divisible by 9 if and only if the sum of its digits is divisible by 9
Solution. If a number \(x\) is expressed in the form \(x_nx_{n-1}\cdots x_0\) this really means the number is equal to \(x_n\times10^{n}+\cdots + x_1\times10+x_0\). Now \(10^n=9k_n+1\) for some \(k_n\) so \(x=(9k_n+1)x_n+\cdots +(9k_1+1)x_1+x_0\). We can rearrange this as \(9(k_nx_n+\cdots +k_1x_1)+x_n+\cdots + x_0\), so by the remainder theorem \(x\) has the same remainder on division by \(9\) as does \(x_n+\cdots + x_0\).
Is \(22051946\) a perfect square ?
We could solve this by computing \(\sqrt{22051946}\) and determining whether it is an integer, or alternatively by squaring various integers and seeing whether \(22051946\) occurs.
There is a much simpler way of seeing that this number cannot be a perfect square.
In Example 2.12 of Chapter 2 we showed that a perfect square must leave a remainder \(0\) or \(1\) when divided by \(4\).
By looking at its last two digits, we see that \[22051946=220519\times 100+46=220519\times 25\times 4+46\] leaves the same remainder as \(46\), and since \(46=11\times 4+2\) this remainder is \(2\). It follows that \(22051946\) is NOT a perfect square.
Show that the last decimal digit of a perfect square cannot be \(2, 3, 7\) or \(8\). Is \(3190491\) a perfect square ?
Let \(n\) be a positive integer, and let \(a\) and \(b\) be any integers. We say that \(a\) is congruent to \(b\text{ mod }(n)\), or \(a\) is a residue of \(b\text{ mod }(n)\), and we write \[a\equiv b\text{ mod }(n)\,,\] if \(a\) and \(b\) leave the same remainder when divided by \(n\). The number \(n\) is referred to as the modulus and the arithmetic of congruences, which we shall describe shortly, is called modular arithmetic.
To calculate residues, we use the Remainder Theorem (Theorem 2.9) to put \(a=qn+r\) with \(0\leq r<n\), and \(b=q'n+r'\) with \(0\leq r'<n\), and then we say that \(a\equiv b\text{ mod }(n)\) if and only if \(r=r'\).
We will often write simply \(a\equiv b\) if it is clear what the value of the modulus \(n\) is.
- \(100\equiv 10\equiv 1\text{ mod }(9)\) in Example 4.1
- \(22051946\equiv 46\equiv 2\text{ mod }(4)\) in Example 4.2.
Show that \(392\equiv1\text{ mod }(23)\).
As you may expect, we will use the notation \(a\not\equiv b\text{ mod }(n)\) to denote that \(a\) and \(b\) are not congruent \(\text{mod }(n)\), in other words if they leave different remainders when divided by \(n\).
Casting out nines
Our first example in this chapter can now be reformulated in the following way:
We can use this fact to solve the following problem.
Show that rearranging the digits of a power of \(2\) cannot yield another power of \(2\). (Here we do not allow rearrangements which bring \(0\) to the front. )
Solution. If we rearrange the digits then the two numbers have the same digit sum and therefore are congruent mod \(9\). Now if we examine the table of powers of \(2\) we see that \(2^0\equiv 1\), \(2^1\equiv 2\), \(2^2\equiv 4\), \(2^3\equiv 8\), \(2^4\equiv 7\), \(2^5\equiv 5\), \(2^6\equiv 1\) and that this pattern then cycles with period 6. So if two powers of \(2\) are congruent mod \(9\) then they are of the form \(2^n\) and \(2^{n+6k}\) for some \(k\). It follows that one of them is at least \(64\) times bigger than the other so they cannot have the same number of digits.
A useful alternative definition of congruence \(\text{mod }(n)\)
For any fixed \(n\geq 1\) we have \(a\equiv b\text{ mod }(n)\) if and only if \(n\,|\,(a-b)\).
Proof. Using the Remainder Theorem we let \(a=qn+r\) and \(b=q'n+r'\) so that \[a-b=(q-q')n+(r-r')\] with \(-n<r-r'<n.\) If \(a\equiv b \text{ mod}~(n)\) then \(r=r'\), so that \(r-r'=0\) and hence \(a-b=(q-q')n\), which is divisible by \(n\). Conversely, if \(n\) divides \(a-b\) then it divides the difference \((a-b)-(q-q')n=r-r'\) and since the only integer strictly between \(-n\) and \(n\) which is divisible by \(n\) is \(0\), then \(r-r'=0\), which means \(r=r'\). Hence \(a\equiv b\text{ mod}~(n)\) as required.
For any \(n\ge 1\),
- \(a\equiv a\) for all integers \(a\);
- if \(a\equiv b\) then \(b\equiv a\);
- if \(a\equiv b\) and \(b\equiv c\) then \(a\equiv c\).
Proof. Let \(n\ge 1\).
- We have \(n|(a-a)\) for all \(a\).
- If \(n|(a-b)\) then clearly \(n|(b-a)\).
- If \(n|(a-b)\) and \(n|(b-c)\) then \(n|\left((a-b)+(b-c)\right)=a-c\).
Equivalence relations
These three properties are the reflexivity, symmetry and transitivity axioms for an equivalence relation. Lemma 4.8 proves that for each fixed \(n\), congruence \(\text{mod }(n)\) is an equivalence relation on \({\mathbb Z}\).
A relation \(\sim\) between elements of some set \(X\) is said to be an equivalence relation if:
- for every \(a\in X\), \(a\sim a\), (the relation is reflexive)
- for every pair \(a,b\in X\), if \(a\sim b\) then \(b\sim a\) (the relation is symmetric),
- for every triple \(a,b,c\in X\), if \(a\sim b\) and \(b\sim c\) then \(a\sim c\) (the relation is transitive).
So the congruence relation \(\equiv\) is an equivalence relation on \(\mathbb Z\).
Let \(f:X\to Y\) be any function. Consider the relation \[ x\sim y\text{ if and only if } f(x)=f(y). \] Then \(\sim\) is an equivalence relation on \(X\).
- \(x\sim x\) as \(f(x)=f(x)\),
- if \(x\sim y\) then \(f(x)=f(y)\) and so \(f(y)=f(x)\) i.e. \(y\sim x\),
- if \(x\sim y\) and \(y\sim z\) then \(f(x)=f(y)\) and \(f(y)=f(z)\) and so \(f(x)=f(z)\) so that \(x\sim z\).
This particular equivalence relation is often referred to as the kernel of the function \(f\).
Partitioning a set
The point of an equivalence relation is to give a way of splitting a set up into subsets (pieces). Given any equivalence relation \(\sim\) on a set \(X\) we define subsets known as the equivalence classes as follows:
For each element \(x\in X\) let \([x]\) denote the subset \(\{y\in X\mid y\sim x\}\)
We will show that each equivalence class \([x]\) is a non-empty subset containing \(x\) itself and that if \([x]\cap [z]\ne\emptyset\) then \([x]=[z]\).
Notice that because \(x \sim x\), the equivalence class \([x]\) contains \(x\) itself. Now suppose that \([x]\cap[z]\ne\emptyset\). Then there is an element \(y\in [x]\cap [z]\). Since \(y\in [x]\), \(y\sim x\), and since \(y\in [z]\), \(y\sim z\). Since \(\sim\) is symmetric, it follows that \(z\sim y\) and \(x\sim y\). Since \(\sim\) is transitive, \(x\sim y\sim z\) implies that \(x\sim z\) so \(x\) also lies in \([z]\).
Now suppose that \(w\in [x]\). Then \(w\sim x\sim z\) implies that \(w\in [z]\). Since this works for ANY \(w\in [x]\) we see that \([x]\subseteq [z]\). Running this argument reversing the roles of \(x\) and \(z\) we can show that \([z]\subseteq[x]\). So \([z]=[x]\) as required.
So have demonstrated that \(X = \cup_{x\in X}{[x]}\) and that \(x \in [x]\) for all \(x\in X\).
A collection of subsets \(P = \{X_i\subseteq X|i\in I\}\) with the property that
is called a partition of the set \(X\).
Let \(X\) be the set of vectors in \(\mathbb R^2\) and for \(u,v\in X\) define \(u\sim v\) to mean that \(u\) and \(v\) have the same length. Then it is clear that
- \(u\sim u\) for all \(u \in X\);
- if \(u\sim v\) then \(v\sim u\) for all \(u,v\in X\);
- if \(u\sim v\) and \(v\sim w\) then \(u\sim w\), for all \(u,v,w\in X\).
Hence \(\sim\) is an equivalence relation on \(X\). Notice that the equivalence class \([(0,1)]\) consists of all vectors of length 1 and so is the unit circle in \(\mathbb R^2\).
Congruence classes
Since \(\equiv_n\) is an equivalence relation by Lemma 4.8, it follows that \({\mathbb Z}\) is partitioned into disjoint equivalence classes. We refer to these as congruence classes. \[{[a]=\{b\in{\mathbb Z}\mid b\equiv a\text{ mod }(n)\}}\] \[{=\{\;\ldots, a-2n, a-n, a, a+n, a+2n, \ldots\,\}}\] for \(a\in{\mathbb Z}\).
Each class corresponds to one of the \(n\) possible remainders \(r=0, 1, \ldots, n-1\) on division by \(n\), so there are \(n\) different congruence classes. They are \[[0]=\{\;\ldots, 2n, -n, 0, n, 2n, \ldots\,\}\] \[[1]=\{\;\ldots, 1-2n, 1-n, 1, 1+n, 1+2n, \ldots\,\}\] \[\vdots\] \[[n-1]=\{\;\ldots, -n-1, -1, n-1, 2n-1, 3n-1, \ldots\,\}\]
There are no further classes distinct from these. For example \[[n]=\{\;\ldots, -n, 0, n, 2n, 3n, \ldots\,\}=[0].\]
It should then be clear that the following important observation is then true. \[[a]=[b]\quad\text{if and only if}\quad a\equiv b\text{ mod }(n)\,.\]
So the following statements all mean the same thing and can be used interchangeably
The following are equivalent:
- \(a\equiv b\text{ mod }~(n)\),
- \(a\) and \(b\) have the same remainder on division by \(n\),
- \(n|(a-b)\),
- \([a] = [b]\).
Notice that when \(n=1\) all integers are congruent to each other, so there is a single congruence class, coinciding with \({\mathbb Z}\). So we gain nothing in this case. For \(n=2\) the two classes \([0]=[0]_2\) and \([1]=[1]_2\) consist of the even and odd integers respectively.
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]=[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 4.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 otherwords, \(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 powers - we shall see later that a restricted form of cancellation can also be defined.
One of the main points of Lemma 4.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 4.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)\).
The least non-negative 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 2.9). 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 2.9 with Exercise 2.11 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 4.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 2.25.
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 4.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 4.17, 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 4.20 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 4.21 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 3.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 2. Translating Theorem 2.29 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 2.29 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 4.25.
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)\).
Solving \(ax\equiv b\) for small \(n\)
In Examples 4.26, 4.27 and 4.30, we had \(n=12\). When \(n\) is small as in these cases, We can simply calculate \(ax\) for each of the \(n\) elements \(x\) of a complete set of residues \(\text{mod }(n)\), and see which of these products are congruent to \(b\).
Solving \(ax\equiv b\) for larger \(n\)
In general however, a more efficient method is needed for solving linear congruences. We shall give an algorithm for this, based on Theorem 4.25, but first we need some preliminary results.
- Let \(m\) divide \(a, b\) and \(n\), and let \(a=a'm,\; b=b'm\) and \(n=n'm\). Then \[ax\equiv b\text{ mod }(n)\quad\text{if and only if}\quad a'x\equiv b'\text{ mod }(n')\,.\]
- Let \(a\) and \(n\) be coprime, let \(m\) divide \(a\) and \(b\), and let \(a=a'm\) and \(b=b'm\). Then \[ax\equiv b\text{ mod }(n)\quad\text{if and only if}\quad a'x\equiv b'\text{ mod }(n)\,.\]
Proof.
We have \(ax\equiv b\) \(\text{mod }(n)\) if and only if \(ax-b=qn\) for some integer \(q\) and so dividing by \(m\), we see that this is equivalent to \(a'x-b'=qn'\), that is, to \(a'x\equiv b'\text{ mod }(n')\).
If \(ax\equiv b\text{ mod }(n)\), then as in (1) we have \(ax-b=qn\) and hence \((a'x-b')m=qn\). It follows that \(m\) divides \(qn\) and since \(m\) is also coprime to \(n\) (\(m\) divides \(a\) and \(a\) is coprime to \(n\)) then \(m\) must divide \(q\) by Corollary 2.25(b). Thus, letting \(q = q'm\) we have that \(a'x-b'=q'n\) is a multiple of \(n\), so \(a'x\equiv b'\text{ mod }(n)\).
Conversely, if \(a'x\equiv b'\text{ mod }(n)\) then \(a'x-b'=q'n\) for some integer \(q'\). Hence, multiplying by \(m\) we see that \(ax-b=mq'n\) and hence \(ax\equiv b\text{ mod }(n)\).
Note that in (1), where \(m\) divides \(a, b\) and \(n\), we divide all three of these integers by \(m\), whereas in (2), where \(m\) divides \(a\) and \(b\), we divide just these two integers by \(m\), leaving \(n\) unchanged. Also note that in part (2) \[ a'x\equiv b'\text{ mod }n\Rightarrow ax\equiv b\mod n \] is always true but \[ ax\equiv b\text{ mod }n\Rightarrow a'x\equiv b'\mod n \] is ONLY true when \(\gcd(a,n)=1\).
Show, by means of a counterexample, that Lemma 4.31(2) can fail if \(a\) and \(n\) are not coprime.
An algorithm to solve \(ax\equiv b\text{ mod }(n)\)
To help you understand each step, it may be useful to try this algorithm out on the congruence \(10x\equiv 6\text{ mod }(14)\) - take a look in Appendix E to see if you are correct.
Step 1
We calculate \(d=\gcd(a,n)\), using the Euclidean algorithm if necessary, and see whether \(d\) divides \(b\). If it does not, there are no solutions, so we stop. If it does, we go on to step 2.
Assuming that there is a solution, Theorem 4.25 will give us the general solution. All we need is to find a particular solution \(x_0\), so the rest of the algorithm focusses on finding \(x_0\). The general strategy is to reduce \(|a|\) until \(|a|=1\), since in this case the solution \(x_0=\pm b\) is obvious.
Step 2
Since \(d\) divides \(a, b\) and \(n\), Lemma 4.31(1) implies that we can replace the original congruence with \[a'x\equiv b'\text{ mod }(n')\,,\] where \(a=a'd,\; b=b'd\) and \(n=n'd\). Note also that by Corollary 2.24, \(a'\) and \(n'\) are coprime. If \(d=1\) then this is nothing practical to do in this step.
Step 3
We now use Lemma 4.31(ii) to “divide” this new congruence by \(m=\gcd(a',b')\), resulting in a congruence \[a''x\equiv b''\text{ mod }(n')\] where \(a'=a''m\), \(b'=b''m\) and \(a''\) is coprime to both \(b''\) and \(n'\). If \(a''=\pm1\) then \(x_0=\pm b''\) is the required solution. Otherwise, we go on to step 4. If \(m=1\) then this is nothing practical to do in this step.
Step 4
There are two ways to proceed at this stage.
- Noting that \[b''\equiv b''\pm n'\equiv b''\pm 2n'\equiv\ldots\text{ mod }(n')\,,\] we may be able to replace \(b''\) with some number \(b'''\equiv b''\text{ mod }n'\) such that \(\gcd(a'',b''')>1\).
- Alternatively, we may be able to multiply the congruence by some suitably chosen constant \(c\), giving \(ca''x\equiv cb''\text{ mod }(n')\), in such a way that the least absolute residue \(a'''\) of \(ca''\) satisfies \(|a'''|<|a''|\). Then we have reduced \(|a''|\) to give a linear congruence \(a'''x\equiv b'''\text{ mod }(n')\) with \(b'''=cb''\).
In both cases, we can then apply step 3 to the new congruence \(a'''x\equiv b'''\text{ mod }(n')\) and again reduce \(|a'''|\). A combination of the methods in step 4 will eventually reduce \(a\) to \(\pm 1\), in which case the solution \(x_0\) can be read off. Theorem 4.25 then gives the general solution.
Consider the congruence \[10x\equiv 6\text{ mod }(14)\,.\]
Solution. Step 1 gives \(\gcd(10,14)=2\), which divides \(6\), so there is a solution. If \(x_0\) is any solution, then the general solution is \(x=x_0+(14/2)t=x_0+7t\), where \(t\in{\mathbb Z}\). To find \(x_0\) go onto step 2 - we divide the original congruence through by \(\gcd(10,14)=2\) to give \[5x\equiv 3\text{ mod }(7)\,.\]
Step 3 has no effect since \(\gcd(5,3)=1\) and so we move on to step 4. We see that \(3\equiv 10\text{ mod }(7)\), with \(10\) divisible by \(5\), we replace the congruence with \[5x\equiv 10\text{ mod }(7)\] and then divide by \(5\) (which is coprime to \(7\)) to give \[x\equiv 2\text{ mod }(7)\,.\] Thus \(x_0=2\) is a solution, so the general solution has the form \[x=2+7t\quad(t\in{\mathbb Z})\,.\]
Consider the congruence \[4x\equiv 13\text{ mod }(47)\,.\]
Solution. Step 1 gives \(\gcd(4,47)=1\), which divides \(13\), so the congruence has solutions. If \(x_0\) is any solution, then the general solution is \(x=x_0+47t\) where \(t\in{\mathbb Z}\), forming a single congruence class \([x_0]\) in \({\mathbb Z}_{47}\). Since \(\gcd(4,47)=1\), step 2 has no effect, so we move on to step 3, which also has no effect since \(\gcd(4,13)=1\). Noting that \(4\times 12=48\equiv 1\text{ mod }(47)\), we multiply by \(12\) to give \[48x\equiv 12\times 13\text{ mod }(47)\,,\] that is, \[x\equiv 3\times 4\times 13\equiv 3\times 52\equiv 3\times 5\equiv 15\text{ mod }(47)\,.\] Thus we can take \(x_0=15\), so the general solution is \(x=15+47t\).
For more practice in solving linear congruences, visit Appendix E in the online version of these notes.
Simultaneous linear congruences
In other words, he wanted to find \(x\) such that the congruences \[x\equiv 2\text{ mod }(3)\,,\quad x\equiv 3\text{ mod }(5)\,,\quad x\equiv 2\text{ mod }(7)\] are simultaneously true. Such problems are thought to have been motivated by observing planetary conjunctions and eclipses.
What do the solutions look like?
Note that if \(x_0\) is any solution, then so is \(x_0+(3\times 5\times 7)t\) for any integer \(t\), so the solutions form a union of congruence classes \(\text{mod }(105)\).
What are the solutions to the simultaneous congruences \[x\equiv 3\text{ mod }(9)\,, x\equiv 2\text{ mod }(6)?\] The simultaneous congruences \(x\equiv 3\text{ mod }(9)\,, x\equiv 2\text{ mod }6\) have no solutions, since if \(x\equiv 3\text{ mod }(9)\) then \(3\) divides \(x\), whereas if \(x\equiv 2\text{ mod }(6)\) then \(3\) does not divide \(x\).
The Chinese Remainder Theorem
The following result, known as the Chinese Remainder Theorem, gives a very satisfactory solution to this type of problem.
Let \(n_1, n_2, \ldots, n_k\) be positive integers, with \(\gcd(n_i, n_j)=1\) whenever \(i\neq j\), and let \(a_1, a_2, \ldots, a_k\) be any integers. Then the solutions of the simultaneous congruences \[x\equiv a_1\text{ mod }(n_1)\,,\quad x\equiv a_2\text{ mod }(n_2)\,,\quad \ldots,\quad x\equiv a_k\text{ mod }(n_k)\] form a single congruence class \(\text{mod }(n)\), where \(n=n_1n_2\ldots n_k\).
An application to counting
Suppose we wish to count a large gathering of people, and we know there are around 80 of them. We can do so using the Chinese remainder theorem as follows:
- [Step 1] Get the people to self organize into groups of \(7\) and count the remainder, \(a_1\),
- [Step 2] Now get them to self organize into groups of \(13\) and count the remainder \(a_2\)
- [Step 3] If \(n\) is the number of people present we now know that \(n\equiv a_1\) mod \((7)\) and \(n\equiv a_2\) mod \(13\). Since \(7\) and \(13\) are coprime we can solve these simultaneous congruences to determine \(n\) mod \(7.13=91\). Since we know that \(n\) is around \(80\) this is enough to determine \(n\).
Of course, to carry out the exercise we need to know how to solve simultaneous congruences. The proof of Theorem 3.10 tells us how to do this.
Proof. Let \(c_in_i=n\), so \(c_i=n_1\ldots n_{i-1}n_{i+1}\ldots n_k\) for each \(i=1, \ldots, k\). Since each of its factors \(n_j\;(j\neq i)\) is coprime to \(n_i\), so is \(c_i\). Corollary 4.29 therefore implies that for each \(i\), the congruence \(c_ix\equiv 1\text{ mod }(n_i)\) has a single congruence class \([d_i]\) of solutions \(\text{mod }(n_i)\). We now claim that the integer \[x_0=a_1c_1d_1+a_2c_2d_2+ \cdots +a_kc_kd_k\] simultaneously satisfies the given congruences, that is, \(x_0\equiv a_i\text{ mod }(n_i)\) for each \(i\). To see this, note that each \(c_j\) (other than \(c_i\)) is divisible by \(n_i\), so \(a_jc_jd_j\equiv 0\text{ mod }n_i\) and hence \(x_0\equiv a_ic_id_i\text{ mod }(n_i)\). But \(c_id_i\equiv 1\text{ mod }n_i\) and so \(x_0\equiv a_i\text{ mod }n_i\) as required. Thus \(x_0\) is a solution of the simultaneous congruences, and it immediately follows that the entire congruence class \([x_0]\) of \(x_0\text{ mod }(n)\) consists of solutions.
To see that this class is unique, suppose that \(x\) is any solution. Then \(x\equiv a_i\equiv x_0\text{ mod }(n_i)\) for all \(i\) and so each \(n_i\) divides \(x-x_0\). Since \(n_1, \dots, n_k\) are mutually coprime, repeated use of Corollary 2.25(a) implies that their product \(n\) also divides \(x-x_0\), so \(x\equiv x_0\text{ mod }(n)\).
Comments
- The proof of Theorem 4.19, which we postponed until later, now follows immediately: given \(n=p_1^{e_1}\ldots p_k^{e_k}\), we put \(n_i=p_i^{e_i}\) for \(i=1, \ldots, k\), so \(n_1, \ldots, n_k\) are mutually coprime with product \(n\); the Chinese Remainder Theorem therefore implies that the solutions of the simultaneous congruences \(x\equiv b\text{ mod }(n_i)\) form a single congruence class \(\text{mod }(n)\); clearly \(b\) is a solution, so these congruences are equivalent to \(x\equiv b\text{ mod }(n)\).
- Note that the proof of the Chinese Remainder Theorem does not merely show that there is a solution for the simultaneous congruences; it also gives us a formula for a particular solution \(x_0\), and hence for the general solution \(x=x_0+nt\;(t\in{\mathbb Z})\). We shall see shortly that there is often an easier method to compute the solution.
Consider our original problem \[x\equiv 2\text{ mod }(3)\,,\quad x\equiv 3\text{ mod }(5)\,,\quad x\equiv 2\text{ mod }(7)\,,\]
Solution. We have \(n_1=3, n_2=5\) and \(n_3=7\), so \(n=105, c_1=35, c_2=21\) and \(c_3=15\). We first need to find a solution \(x=d_1\) of \(c_1x\equiv 1\text{ mod }(n_1)\), that is, \(35x\equiv 1\text{ mod }(3)\); this is equivalent to \(-x\equiv 1\text{ mod }(3)\), so we can take \(x=d_1=-1\) for example.
Similarly, \(c_2x\equiv 1\text{ mod }(n_2)\) gives \(21x\equiv 1\text{ mod }(5)\), that is, \(x\equiv 1\text{ mod }(5)\), so we can take \(x=d_2=1\), while \(c_3x\equiv 1\text{ mod }(n_3)\) gives \(15x\equiv 1\text{ mod }(7)\), that is, \(x\equiv 1\text{ mod }(7)\), so we can also take \(x=d_3=1\).
Of course, different choices of \(d_i\) are possible here, leading to different values of \(x_0\), but they will all give the same congruence class of solutions \(\text{mod }(105)\).
We now have \[x_0=a_1c_1d_1+a_2c_2d_2+a_3c_3d_3 =2.35.(-1)+3.21.1+2.15.1=23\,,\] so the solutions form the congruence class \([23]\text{ mod }(105)\), that is, the general solution is \(x=23+105t\;(t\in{\mathbb Z})\).
We can also use the Chinese Remainder Theorem as the basis for a second method for solving simultaneous linear congruences, which is often more efficient.
We start by finding a solution \(x=x_1\) to one of the congruences - usually it is best to start with the congruence involving the largest modulus, for reasons that should become apparent. We illustrate by considering the congruences in Example 4.37. Starting with \(x\equiv 2\text{ mod }(7)\), which has \(x_1=2\) as an obvious solution, and so the ‘general solution’ for this congruence is \[ x = 2 + 7t, t\in\mathbb Z. \]
Notice that there is no real work involved at this point. We want this general solution to also satisfy the other congruences, so taking the next highest modulus we require \[ 2+7t\equiv 3\text{ mod }(5), \] or equivalently \(7t\equiv1\text{ mod }(5)\). We solve this using our 4-point algorithm as in previous examples: Since \(7\equiv2\text{ mod }(5)\) we can simplify to \[ 2t\equiv1\equiv6\text{ mod }(5) \] and so \(t\equiv3\text{ mod }(5)\). Hence \(t = 3 + 5s\) for \(s\in\mathbb Z\) and so \(x = 2+7t = 2+7(3+5s) = 23+35s\) for \(s\in\mathbb Z\). This is then the general solution for the simultaneous congruences \[ x\equiv 3\text{ mod }(5)\,,\quad x\equiv 2\text{ mod }(7)\,. \]
Notice how starting with the modulus with the highest value, reduces the coefficient in front of \(t\) immediately, and makes for an easier solution.
We now want this solution to satisfy our final congruence \(x\equiv2\text{ mod }(3)\) and so we solve \[ 23+35s\equiv2\text{ mod }(3). \] Since \(23\equiv2\text{ mod }(3)\) and \(35\equiv2\text{ mod }(3)\) then we have \[ 2s\equiv0\text{ mod }(3) \] which has a solution of \(s\equiv0\text{ mod }(3)\) or \(s = 3r\) for \(r\in\mathbb Z\). Hence \(x = 23 + 35(3r) = 23 + 105r\) for \(r\in\mathbb Z\) is the general solution to all three congruences. Notice that this method only involves solving 2 congruences, whereas the method in the proof of Theorem 4.36 involves solving three (to find the values \(d_1, d_2\) and \(d_3\)).
Solve the simultaneous congruences \[x\equiv 1\text{ mod }(4),\quad x\equiv 2\text{ mod }(3),\quad x\equiv 3\text{ mod }(5)\,.\]
Solve the simultaneous congruences \[x\equiv 2\text{ mod }(7),\quad x\equiv 7\text{ mod }(9),\quad x\equiv 3\text{ mod }(4)\,.\]
Generalising the CRT
The linear congruences in the Chinese Remainder Theorem are all of the form \(x\equiv a_i\) mod \((n_i)\). If we are given a set of simultaneous linear congruences, with one (or more) of them in the more general form \(ax\equiv b\text{ mod }(n_i)\), then we will first need to use the earlier algorithm to solve this congruence, expressing its general solution as a congruence class modulo some divisor of \(n_i\); it will then be possible to apply the techniques based on the Chinese Remainder Theorem to solve the resulting simultaneous congruences.
Consider the simultaneous congruences \[7x\equiv 3\text{ mod }(12),\quad 10x\equiv 6\text{ mod }(14)\,.\]
Solution. We saw in Examples 11 and 12 that the first of these congruences has the general solution \(x=9+12t\), and that the second has the general solution \(x=2+7t\).
It follows that we can replace the original pair of congruences with the pair \[x\equiv 9\text{ mod }(12),\quad x\equiv 2\text{ mod }(7)\,.\]
Clearly, \(x_0=9\) is a particular solution; since the moduli \(12\) and \(7\) are coprime, with product \(84\), the Chinese Remainder Theorem implies that the general solution has the form \(9+84t\).
Solve the simultaneous congruences \[3x\equiv 6\text{ mod }(12),\quad 2x\equiv 5\text{ mod }(7),\quad 3x\equiv 1\text{ mod }(5)\,.\]
Simplifying congruences
The Chinese Remainder Theorem can be used to convert a single congruence, with a large modulus, into several simultaneous congruences with smaller moduli, which may be easier to solve.
Consider the linear congruence \[13x\equiv 71\text{ mod }(380)\,.\]
Solution. Instead of using the algorithm described earlier for solving a single linear congruence, we can use the factorisation \(380=2^2\times 5\times 19\), together with Theorem 4.19, to replace this congruence with the three simultaneous congruences \[13x\equiv 71\text{ mod }(4)\,,\quad 13x\equiv 71\text{ mod }(5)\,,\quad 13x\equiv 71\text{ mod }(19)\,.\]
These immediately reduce to
\[x\equiv 3\text{ mod }(4)\,,\quad 3x\equiv 1\text{ mod }(5)\,,\quad 13x\equiv 14\text{ mod }(19)\,.\]
The first of these needs no further simplification, but we can apply the single congruence algorithm to simplify each of the other two.
We write the second congruence as \(3x\equiv 6\text{ mod }(5)\), so dividing by \(3\) (which is coprime to \(5\)) we get \(x\equiv 2\text{ mod }(5)\).
Similarly, the third congruence can be written as \(-6x\equiv 14\text{ mod }(19)\), so dividing by \(-2\) we get \(3x\equiv -7\equiv 12\text{ mod }(19)\), and now dividing by \(3\) we have \(x\equiv 4 \text{ mod }(19)\).
Our original congruence is therefore equivalent to the simultaneous congruences \[x\equiv 3\text{ mod }(4)\,,\quad x\equiv 2\text{ mod }(5)\,,\quad x\equiv 4\text{ mod }(19)\,.\] Now these have mutually coprime moduli, so the Chinese Remainder Theorem applies, and we can use either of our two methods to find the general solution.
Using the second method, we start with a solution \(x_1=4\) of the third congruence; adding and subtracting multiples of \(19\), we find that \(x_2=42\) also satisfies the second congruence, and then adding and subtracting multiples of \(19\times 5=95\) we find that \(327\) (or equivalently \(-53\)) also satisfies the first congruence. Thus the general solution has the form \(x=327+380t\;(t\in{\mathbb Z})\).
Solve the congruence \(91x\equiv 419\text{ mod }(440)\).