4.5: Linear Congruences

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

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 \left(mod\, \dfrac{m}{\gcd(c,m)}\right)$

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)\}=\left\{x_0, x_0+\dfrac{m}{d}, x_0+\dfrac{2m}{d},\ldots, x_0+\dfrac{(d-1)m}{d}\right\}$, 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)\}=\left\{x_0, x_0+\dfrac{m}{d}, x_0+\dfrac{2m}{d},\ldots, x_0+\dfrac{(d-1)m}{d} \right\}$, 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{6}$

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

Answer

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