# 4.5: Linear Congruences

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

## Linear Congruences

##### Definition: Linear Congruences

A linear congruences in one variable  has the form $$ax \equiv b (mod \,m)$$, where $$m \in \mathbb{Z}_+$$, $$a,b \in \mathbb{Z}$$ and $$x \in \mathbb{Z}$$ is a variable.

A linear congruence is similar to a linear equation, solving linear congruence means finding all integer $$x$$ that makes, $$ax \equiv b (mod \,m)$$ true. In this case, we will have only a finite solution in the form of $$x \equiv (mod \,m)$$. Thus there will be at most $m$ solutions, namely $$0,1, \ldots, m-1.$$

Thus, a linear congruence in one variable $$x$$ is of the form $$ax \equiv b(mod \, m)$$, where $$a,b \in \mathbb{Z}$$ and $$m \in \mathbb{Z_+}$$. This form of linear congruence has at most $$m$$ solutions.)  In this section, we shall assume $$a (\ne 0) \in \mathbb{Z}$$.

Method I: We can find the solutions to a linear congruence, by checking all possible $$0,1, \ldots, m-1.$$

Example $$\PageIndex{1}$$:

Find all solutions to  $$x \equiv 6 ( mod \,11 )$$, between $$0$$ and $$10$$ inclusive.

Solution

Possible solutions are $$0, 1,2, \ldots, 10$$. The only solution is $$6$$.

Example $$\PageIndex{2}$$:

Find all solutions to $$2x \equiv 3 ( mod \,7 )$$, between $$0$$ and $$6$$ inclusive.

Solution

Possible solutions are $$0, 1,2, \ldots, 6$$. The only solution is $$4$$.

Example $$\PageIndex{3}$$:

Solve $$3x \equiv 1 ( mod \,8 )$$.

Solution

Possible solutions are $$0, 1,2, \ldots, 7$$. The only solution is $$3$$.

##### Example $$\PageIndex{4}$$

Find all solutions to $$3x \equiv 1 ( mod \,6 )$$, between $$0$$ and $$5$$ inclusive.

###### Solution

Possible solutions are $$0, 1,2,3,4, 5$$. In this case $$3x( mod \,6 )$$ is $$0,3,0,3,0,3$$. Thus, $$3x \equiv 1 ( mod \,6 )$$ has no solutions.

Example $$\PageIndex{5}$$:

Solve $$2x \equiv 2 ( mod \,4 )$$.

Solution

Possible solutions are $$0, 1,2, 3$$. The solutions are $$1$$ and $$3$$.

The following theorems give a criterion for the solvability of $$ax \equiv b(mod \, m)$$.

Method II:

Theorem $$\PageIndex{1}$$

Let $$m \in \mathbb{Z}_+$$ and  $$a,b, c\in \mathbb{Z}$$. If $$\gcd(c,m)=1$$ and $$ac \equiv bc (mod\, m)$$ then $$a \equiv b (mod\, m)$$

Proof

Let $$m \in \mathbb{Z}_+$$ and  $$a,b, c\in \mathbb{Z}$$. Assume that $$\gcd(c,m)=1$$ and $$ac \equiv bc (mod\, m)$$. Since $$ac \equiv bc (mod\, m)$$, $$ac-bc=mn,$$ for $$n\in \mathbb{Z}.$$ Thus $$(a-b)c=mn$$. Thus $$m \mid (a-b)c$$. Since $$\gcd(c,m)=1$$,  $$m \mid (a-b)$$. Hence, $$a \equiv b (mod\, m)$$.

##### Example $$\PageIndex{6}$$

Solve $$3x \equiv 1 ( mod \,8 )$$.

###### Solution

We will solve using the above theorem.  $$3x \equiv 1 \equiv 9 ( mod \,8 )$$. Hence,  $$x \equiv 3 ( mod \,8 )$$.

##### Theorem $$\PageIndex{2}$$

Let $$m \in \mathbb{Z}_+$$ and  $$a,b, c\in \mathbb{Z}$$. Then $$ac \equiv bc (mod\, m)$$ if and only if  $$a \equiv b (mod\, \dfrac{m}{\gcd(c,m)})$$

Proof

TBA

##### Example $$\PageIndex{7}$$

Solve $$9x \equiv 6 ( mod \,24 )$$.

###### Solution

Since $$\gcd(3,24)=3,$$, $$3x \equiv 2 ( mod \,8 ) .$$ Thus $$3x \equiv 2 \equiv 10 \equiv 18 ( mod \,8 ).$$ Hence $$x \equiv 6 ( mod \,8 )$$.

The above two methods are tedious when the numbers are large.

##### Theorem $$\PageIndex{3}) Let \(m \in \mathbb{Z}_+$$ and  $$a,b \in \mathbb{Z}$$, with $$a$$ be non-zero. Then

$$ax \equiv b(mod\, m)$$ has a solution if and only if $$\gcd(a,m) |b$$. Moreover, if $$x=x_0$$ is a particular solution to this congruence, then the set of all solutions is $$\{x \in \mathbb{Z} | x \equiv x_0(mod\, m)\}=\{x_0, x_0+\dfrac{m}{d}, x_0+\dfrac{2m}{d},\ldots, x_0+\dfrac{(d-1)m}{d}\}$$, where $$d=\gcd(a,m).$$

Proof

TBA

### We will see below how to find the solution for a particular case: Using Multiplicative inverse modulo m

Let $$m \in \mathbb{Z}_+.$$  Let $$a \in \mathbb{Z}$$ such that $$a$$ and $$m$$ are relatively prime. Then there exist integers $$x$$ and $$y$$ such that $$ax+my=1.$$ Then  $$ax \equiv 1 ( mod \,m )$$. Note that $$1$$ is the multiplicative identity on $$mod \,m$$. In this case, $$x (mod \,m)$$ is the inverse of $$a (mod \,m)$$.

Theorem $$\PageIndex{3}$$

If $$\gcd(a,m)=1$$ then $$ax \equiv b(mod \, m)$$ has a unique solution $$x \equiv a^{-1}b(mod \, m).$$ Thus, the set of all solutions is $$\{x \in \mathbb{Z} | x \equiv a^{-1}b(mod \, m)\}.$$

Proof

Since $$\gcd(a,m)=1$$, therefore $$a$$ has an inverse $$a^{-1} \mod m$$. Hence $$x \equiv a^{-1}b(mod \, m).$$

##### Example $$\PageIndex{8}$$

Solve $$16x \equiv 11 ( mod \,35)$$.

###### Solution

Since $$16x \equiv 11 ( mod \,35)$$, $$x \equiv (16)^{-1}11 ( mod \,35) \equiv (11)(11) ( mod \,35) \equiv 16 ( mod \,35).$$

The following theorem guides on solving linear congruence. However, we will discuss it after learning the linear Diophantine equations.

##### Theorem $$\PageIndex{4}) Let \(m \in \mathbb{Z}_+$$ and  $$a,b \in \mathbb{Z}$$, with $$a$$ be non-zero. Then the  linear congruence

$$ax \equiv b(mod\, m)$$ has a solution if and only if $$\gcd(a,m) |b$$. Moreover, if $$x=x_0$$ is a particular solution to this congruence, then the set of all solutions is $$\{x \in \mathbb{Z} | x \equiv x_0(mod\, m)\}=\{x_0, x_0+\dfrac{m}{d}, x_0+\dfrac{2m}{d},\ldots, x_0+\dfrac{(d-1)m}{d}\}$$, where $$d=\gcd(a,m).$$

## The Chinese Remainder Theorem

In this section, we will explore solving simultaneous linear congruences.

Theorem $$\PageIndex{5}$$

Let $$a, b \in \mathbb{Z}$$ and $$n,m \in \mathbb{N}$$ such that $$\gcd(n,m) = 1$$. Then there exists  $$x \in \mathbb{Z}$$ such that $$x \equiv a(mod\, n)$$ and $$x \equiv b(mod\, m)$$. Moreover $$x$$ is unique modulo $$mn$$.

Example $$\PageIndex{5}$$:

Solve $$x \equiv 2 (mod\, 3)$$ and $$x \equiv 3 (mod\, 5)$$.

Solution

Since $$x \equiv 2 (mod\, 3)$$, the possible solutions are $$2, 5, 8, 11, 15, \ldots$$.

Since $$x \equiv 3 (mod\, 5)$$, the possible solutions are $$3, 8, 13, \ldots$$.

Then $$x=8$$. Since any $$y$$ such that $$y \equiv 8 (mod\, 15)$$ are also solutions, we have $$23, 38, \cdots$$

##### Theorem $$\PageIndex{6}$$: Chinese Remainder Theorem

Let $$a_1, \cdots, a_k \in \mathbb{Z}$$ and $$m_1,\cdots, m_k \in \mathbb{N}$$ such that $$\gcd(m_i,m_j) = 1$$, for all $$i \ne j$$. Then there  exists $$x \in \mathbb{Z}$$ such that

$\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_k \pmod{m_k} \end{cases}$.

Moreover $$x$$ is unique modulo $$m_1 \ldots m_k$$.

##### Note

Solving Congruences, using Chinese Remainder Theorem

Let $\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_k \pmod{m_k} \end{cases}$.

Then

Step 1: Calculate the product  $$M = m_1 \times m_2 \times \ldots \times m_k$$.

Step 2: Calculate the Modulus Factors.  For each $$m_i$$, calculate $$M_i = \frac{M}{m_i}$$.

Step 3: Compute the Inverses.  For each $$M_i$$, compute the modular inverse $$M_i^{-1}$$ modulo $$m_i$$.

Step 4: Combine Solutions. Finally, the solution $$x$$ to the system of congruences is given by: $x = \left( \sum_{i=1}^{k} a_i M_i M_i^{-1} \right) \mod M$

We can use the following table to compute all the listed variables.

 $$a_i$$ $$m_i$$ $$M_i$$ $$M_i^{-1}$$ $$M$$

##### Example $$\PageIndex{1}$$

Solve $\begin{cases} x \equiv 3 \pmod{5} \\ x \equiv 1 \pmod{7} \\ x \equiv 6 \pmod{8} \end{cases}$.

 $$a_i$$ $$m_i$$ $$M_i$$ $$M_i^{-1}$$ $$M$$ 3 5 $$\dfrac{280}{5}=56$$ $$1$$ 280 1 7 $$\dfrac{280}{7}=40$$ $$3$$ 280 6 8 $$\dfrac{280}{8}=35$$ $$3$$ 280

First we calculate $$M=(5)(7)(8) 280.$$  Now we can calculate $$M_1,M_2$$ and $$M_3$$.

Next we calculate $$M_1^{-1},M_2^{-1}$$ and $$M_3^{-1}$$.

To calculate $$M_1^{-1}$$: we need to solve $$56x_1 \equiv 1\pmod{5}.$$ Place these values into the table.

Now, $$x \equiv ((3)(56)(1)+(7)(40(3)+(8)(35)(3)) \pmod{280} \equiv 918 \pmod{280} \equiv 78 \pmod{280}.$$

This page titled 4.5: Linear Congruences is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Pamini Thangarajah.