A linear congruence in one variable \(x\) is a congruence of the form \(ax\equiv b \:\left(\mathrm{mod}\: n \right)\),
for some integers \(a\) and \(b\). We study solutions of linear congruences such as \(9x\equiv 6 \:\left(\mathrm{mod}\: 15\right)\).
Theorem.
Let \(a\), \(b\), and \(n\) be positive integers where \(d=\gcd(a,n)\).
\(ax\equiv b \:\left(\mathrm{mod}\: n \right)\) has a solution if and only if \(d\) divides \(b\).
If \(d\vert b\), then there are \(d\) incongruent solutions modulo \(n\): \(x_0+i\frac{n}{d}\), \(i=0,1,\ldots,d-1\)
where \(ax_0\equiv b \:\left(\mathrm{mod}\: n \right)\).
Proof.
1. Suppose \(ax\equiv b \:\left(\mathrm{mod}\: n \right)\) has a solution \(c\). Then \(ac\equiv b \:\left(\mathrm{mod}\:n \right)
\implies ac-b=kn\) for some integer \(k\). Since \(d=\gcd(a,n)\) divides \(a\) and \(n\), \(d\) divides \(b=ac-kn\).
Conversely let \(d=\gcd(a,n)\) divides \(b\), i.e., \(b=td\) for some integers \(t\). By Bézout's Lemma
\(d=ar+ns\) for some integers \(r\) and \(s\). Then \(td=tar+tns\) which implies
\[ b=a(tr)+n(ts)\implies a(tr)=b+n(-ts)\implies a(tr)\equiv b \:\left(\mathrm{mod}\:n \right).\]
2. Suppose \(d\vert b\) and \(ax_0\equiv b \:\left(\mathrm{mod}\: n \right)\). Consider a solution \(x\) of
\(ax\equiv b \:\left(\mathrm{mod}\: n \right)\). Note \(ax-ax_0\equiv b-b \:\left(\mathrm{mod}\: n \right)\),
i.e., \(a(x-x_0)\equiv 0 \:\left(\mathrm{mod}\: n \right)\). Then dividing both sides by \(a\),
\(x-x_0\equiv 0 \:\left(\mathrm{mod}\:{\frac{n}{d}} \right)\) by a previous theorem. So \(x=x_0+i\frac{n}{d}\) for some integer
\(i\). To get incongruent solutions modulo \(n\), consider a solution \(x'=x_0+j\frac{n}{d}\) for some integer \(j\).
If \(x\) and \(x'\) are congruent modulo \(n\), then
\[ x_0+i\frac{n}{d}\equiv x_0+j\frac{n}{d} \:\left(\mathrm{mod}\: n \right)\implies i\frac{n}{d}\equiv j\frac{n}{d} \:\left(\mathrm{mod}\: n \right).\]
Since \(\gcd(\frac{n}{d},n)=\frac{n}{d}\), dividing both sides by \(\frac{n}{d}\), by a previous theorem we get
\[ i\equiv j \:\left(\mathrm{mod}\:{n/\left(\frac{n}{d}\right)} \right)\implies i\equiv j \:\left(\mathrm{mod}\:d \right).\]
Thus the incronguent solutions modulo \(n\) are \(x=x_0+i\frac{n}{d}\) where \(i\) runs over incronguent integers modulo \(d\)
such as \(i=0,1,\ldots,d-1\).
◼
Corollary. Suppose \(\gcd(a,n)=1\). Then
\(ax\equiv b \:\left(\mathrm{mod}\: n \right)\) has a unique solution modulo \(n\), and
\(ax\equiv 1 \:\left(\mathrm{mod}\: n \right)\) has a unique solution modulo \(n\) which is denoted by \(a^{-1}\)
modulo \(n\).
Example.
\(9x\equiv 6 \:\left(\mathrm{mod}\: 15 \right)\) has a solution because \(\gcd(9,15)=3\) divides \(6\). Since \(\gcd(9,15)=3\),
there are three incongruent solutions modulo \(15\):
\[ x\equiv x_0,\; x_0+1\cdot 5,\; x_0+2\cdot 5 \:\left(\mathrm{mod}\: 15\right),\]
where \(x_0\) is a particular solution modulo \(15\). There are a couple of ways to find \(x_0\):
We find \(\gcd(9,15)=3\) by the Euclidean Algorithm:
\[ \begin{align*}
15 &=1\cdot 9+6,\\
9 &=1\cdot 6+3\\
6 &=2\cdot 3.
\end{align*} \]
So \(3=9-1\cdot 6=9-(15-1\cdot 9)=2\cdot 9 -1\cdot 15.\) So \(9\cdot 2=3+1\cdot 15\). Multiplying by \(2\), we get
\(9\cdot 4=6+2\cdot 15\), i.e., \(x_0=4\) is a solution to \(9x\equiv 6 \:\left(\mathrm{mod}\: 15 \right)\). Thus three incongruent
solutions modulo \(15\) are \(x\equiv 4,\; 9,\; 14 \:\left(\mathrm{mod}\: 15 \right)\).
To find \(x_0\), first divide \(9x\equiv 6 \:\left(\mathrm{mod}\: 15 \right)\) by \(\gcd(9,15)=3\) and get
\(3x\equiv 2 \:\left(\mathrm{mod}\: 5 \right)\).
(a) Since \(\gcd(3,5)=1\), there is a unique solution which is one of \(0,1,2,3,4\). So start multiplying \(3\) by each of them
until we get \(2\) modulo \(5\):
\[ 3\cdot 0 \not\equiv 2 \:\left(\mathrm{mod}\: 5 \right),\; 3\cdot 1 \not\equiv 2 \:\left(\mathrm{mod}\: 5 \right),\;
3\cdot 2 \not\equiv 2 \:\left(\mathrm{mod}\: 5 \right),\; 3\cdot 3 \not\equiv 2 \:\left(\mathrm{mod}\: 5 \right),\;
3\cdot 4 \equiv 2 \:\left(\mathrm{mod}\:5 \right).\]
Then \(x_0=4\) is a solution to \(3x\equiv 2 \:\left(\mathrm{mod}\:5\right)\) and consequently to
\(9x\equiv 6 \:\left(\mathrm{mod}\: 15\right)\).
(b) Alternatively multiply both sides of \(3x\equiv 2 \:\left(\mathrm{mod}\:5\right)\) by \(3^{-1}\) modulo \(5\).
So start multiplying \(3\) by \(2,3,4\) until we get \(1\) modulo \(5\):
\[ 3\cdot 2 \equiv 1 \:\left(\mathrm{mod}\:5 \right)\implies 3^{-1} \equiv 2 \:\left(\mathrm{mod}\:5 \right).\]
Then \(2\cdot 3x\equiv 2\cdot 2 \:\left(\mathrm{mod}\:5 \right)\implies x\equiv 4 \:\left(\mathrm{mod}\:5 \right)\).
So \(x_0=4\) is a solution to \(3x\equiv 2 \:\left(\mathrm{mod}\:5\right)\) and consequently to
\(9x\equiv 6 \:\left(\mathrm{mod}\: 15\right)\).
Thus three incongruent solutions modulo \(15\) are \(x\equiv 4,\; 9,\; 14 \:\left(\mathrm{mod}\: 15 \right)\).
Now we study systems of linear congruences such as
\[ \begin{align*}
x &\equiv 2 \:\left(\mathrm{mod}\: 3 \right),\\
x &\equiv 3 \:\left(\mathrm{mod}\: 5 \right),\\
x &\equiv 2 \:\left(\mathrm{mod}\: 7 \right).
\end{align*}\]
This is the formulation of the following problem found in the third century Chinese book Sunzi Suanjing by Sunzi:
Find an integer that leaves remainder \(2\) when divided by \(3\), remainder \(3\) when divided by \(5\), and remainder \(2\)
when divided by \(7\).
Now we solve the system directly by a general technique as follows:
\(x\equiv 2 \:\left(\mathrm{mod}\: 3 \right) \implies x=2+3r\). Plugging it in \(x\equiv 3 \:\left(\mathrm{mod}\: 5 \right)\),
we get \((2+3r)\equiv 3 \:\left(\mathrm{mod}\: 5 \right)\implies 3r\equiv 1 \:\left(\mathrm{mod}\: 5 \right)\implies 6r\equiv 2
\:\left(\mathrm{mod}\: 5 \right)\implies r\equiv 2 \:\left(\mathrm{mod}\: 5 \right)\implies r=2+5s\).
Plugging it in \( x=2+3r\), we get \(x=2+3(2+5s)=8+15s\). Plugging it in \(x\equiv 2 \:\left(\mathrm{mod}\: 7 \right)\),
we get \( (8+15s)\equiv 2 \:\left(\mathrm{mod}\: 7 \right)\implies 15s\equiv -6 \:\left(\mathrm{mod}\: 7 \right) \implies
s\equiv 1 \:\left(\mathrm{mod}\: 7 \right)\implies s=1+7t\). Plugging it in \(x=8+15s\) we get \(x=8+15(1+7t)=23+105t\implies
x\equiv 23 \:\left(\mathrm{mod}\: 105 \right)\).
Theorem.(Chinese Remainder Theorem)
If positive integers \(n_1,n_2,\ldots,n_k\) are pairwise relatively prime, then the following system of linear congruences has
a unique solution modulo \(n_1n_2\cdots n_k\):
\[ x\equiv a_1 \:\left(\mathrm{mod}\: n_1 \right),\; x\equiv a_2 \:\left(\mathrm{mod}\: n_2 \right),\ldots,\; x\equiv a_k
\:\left(\mathrm{mod}\: n_k \right).\]
Proof.
Suppose positive integers \(n_1,n_2,\ldots,n_k\) are pairwise relatively prime. Let \(n=n_1n_2\cdots n_k\).
Let \(N_i=n/n_i\) for \(i=1,2,\ldots,k\). Since \(\gcd(n_i,n_j)=1\) for all \(j\neq i\), \(\gcd(n_i,N_i)=1\) which implies
\(N_ix=1 \:\left(\mathrm{mod}\: n_i\right) \) has a unique solution, say \(y_i\). We show that
\[ y:=y_1a_1N_1+y_2a_2N_2+\cdots+y_ka_kN_k\]
is a simultaneous solution to the system, i.e., \(y\equiv a_i \:\left(\mathrm{mod}\: n_i \right)\) for \(i=1,2,\ldots,k\).
Since \(n_i\vert N_j\) for all \(j\neq i\), \(N_j\equiv 0 \:\left(\mathrm{mod}\: n_i \right)\) for all \(j\neq i\) and
consequently
\[ y=y_1a_1N_1+y_2a_2N_2+\cdots+y_ka_kN_k \equiv a_iy_iN_i \:\left(\mathrm{mod}\: n_i \right).\]
Since \(N_iy_i \equiv 1 \:\left(\mathrm{mod}\: n_i \right)\), \(a_iy_iN_i \equiv a_i \:\left(\mathrm{mod}\: n_i\right)\).
Thus
\[ y=y_1a_1N_1+y_2a_2N_2+\cdots+y_ka_kN_k \equiv y_ia_iN_i \equiv a_i \:\left(\mathrm{mod}\: n_i \right).\]
To show the uniqueness of the solution \(y\) modulo \(n\), let \(z\) be a simultaneous solution. Then
\(y\equiv z\equiv a_i \:\left(\mathrm{mod}\: n_i \right)\) for \(i=1,2,\ldots,k\). So \(n_i\vert (z-y)\) for
\(i=1,2,\ldots,k\). Since \(n_1,n_2,\ldots,n_k\) are pairwise relatively prime, \(n_1n_2\cdots n_k\vert (z-y)\)
by a previous corollary. Thus \(z\equiv y \:\left(\mathrm{mod}\: n \right) \).
◼
Example. Let us solve
\(x\equiv 2 \:\left(\mathrm{mod}\: 3\right),\; x\equiv 3 \:\left(\mathrm{mod}\: 5\right),\; x\equiv 2 \:\left(\mathrm{mod}\: 7\right)\).
Let \(n=3\cdot 5\cdot 7=105\). Let \(N_1=n/3=35\), \(N_2=n/5=21\), and \(N_3=n/7=15\). Now linear congruences
\[ 35x\equiv 1 \:\left(\mathrm{mod}\: 3\right),\; 21x\equiv 1 \:\left(\mathrm{mod}\: 5 \right),\; 15x\equiv 1
\:\left(\mathrm{mod}\: 7 \right)\]
have unique solutions \(x=2,1,1\) respectively. Then \[ y=y_1a_1N_1+y_2a_2N_2++y_3a_3N_3=2\cdot 2\cdot 35+1\cdot 3\cdot 21+1\cdot 2\cdot 15=233.\]
Thus the unique solution is \(233\equiv 23 \:\left(\mathrm{mod}\: 105 \right)\).
Note that a linear congruence with large integers can be converted into a system of linear congruences with smaller integers.
For example, consider \(x\equiv 6 \:\left(\mathrm{mod}\: 105 \right)\). Since \(105=3\cdot 5\cdot 7\), it can be converted
to the system
\[ x\equiv 6 \:\left(\mathrm{mod}\: 3\right),\; x\equiv 6 \:\left(\mathrm{mod}\: 5\right),\; x\equiv 6 \:\left(\mathrm{mod}\: 7\right).\]
This technique together with CRT is useful in integer arithmetic in computers.