Number Theory Home

## Linear Congruences

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)$$.

1. $$ax\equiv b \:\left(\mathrm{mod}\: n \right)$$ has a solution if and only if $$d$$ divides $$b$$.
2. 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

1. $$ax\equiv b \:\left(\mathrm{mod}\: n \right)$$ has a unique solution modulo $$n$$, and
2. $$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$$:

1. 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)$$.

2. 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.

Last edited