1.5 Linear Congruence

Last updated
Save as PDF

Page ID: 163792

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

$ \newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$ \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$ \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vectorC}[1]{\textbf{#1}} $

$ \newcommand{\vectorD}[1]{\overrightarrow{#1}} $

$ \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} $

$ \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} $

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

$\newcommand{\avec}{\mathbf a}$ $\newcommand{\bvec}{\mathbf b}$ $\newcommand{\cvec}{\mathbf c}$ $\newcommand{\dvec}{\mathbf d}$ $\newcommand{\dtil}{\widetilde{\mathbf d}}$ $\newcommand{\evec}{\mathbf e}$ $\newcommand{\fvec}{\mathbf f}$ $\newcommand{\nvec}{\mathbf n}$ $\newcommand{\pvec}{\mathbf p}$ $\newcommand{\qvec}{\mathbf q}$ $\newcommand{\svec}{\mathbf s}$ $\newcommand{\tvec}{\mathbf t}$ $\newcommand{\uvec}{\mathbf u}$ $\newcommand{\vvec}{\mathbf v}$ $\newcommand{\wvec}{\mathbf w}$ $\newcommand{\xvec}{\mathbf x}$ $\newcommand{\yvec}{\mathbf y}$ $\newcommand{\zvec}{\mathbf z}$ $\newcommand{\rvec}{\mathbf r}$ $\newcommand{\mvec}{\mathbf m}$ $\newcommand{\zerovec}{\mathbf 0}$ $\newcommand{\onevec}{\mathbf 1}$ $\newcommand{\real}{\mathbb R}$ $\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$ $\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$ $\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$ $\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$ $\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$ $\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$ $\newcommand{\laspan}[1]{\text{Span}\{#1\}}$ $\newcommand{\bcal}{\cal B}$ $\newcommand{\ccal}{\cal C}$ $\newcommand{\scal}{\cal S}$ $\newcommand{\wcal}{\cal W}$ $\newcommand{\ecal}{\cal E}$ $\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$ $\newcommand{\gray}[1]{\color{gray}{#1}}$ $\newcommand{\lgray}[1]{\color{lightgray}{#1}}$ $\newcommand{\rank}{\operatorname{rank}}$ $\newcommand{\row}{\text{Row}}$ $\newcommand{\col}{\text{Col}}$ $\renewcommand{\row}{\text{Row}}$ $\newcommand{\nul}{\text{Nul}}$ $\newcommand{\var}{\text{Var}}$ $\newcommand{\corr}{\text{corr}}$ $\newcommand{\len}[1]{\left|#1\right|}$ $\newcommand{\bbar}{\overline{\bvec}}$ $\newcommand{\bhat}{\widehat{\bvec}}$ $\newcommand{\bperp}{\bvec^\perp}$ $\newcommand{\xhat}{\widehat{\xvec}}$ $\newcommand{\vhat}{\widehat{\vvec}}$ $\newcommand{\uhat}{\widehat{\uvec}}$ $\newcommand{\what}{\widehat{\wvec}}$ $\newcommand{\Sighat}{\widehat{\Sigma}}$ $\newcommand{\lt}{<}$ $\newcommand{\gt}{>}$ $\newcommand{\amp}{&}$ $\definecolor{fillinmathshade}{gray}{0.9}$

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

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

\(a_i\)	\(m_i\)	\(M_i\)	\(M_i^{-1}\)	\(M\)

\(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

Search

Text Color

Text Size

Margin Size

Font Type

Linear Congruences

Definition: Linear Congruences

Example \(\PageIndex{4}\)

Solution

Example \(\PageIndex{6}\)

Solution

Theorem \(\PageIndex{2}\)

Example \(\PageIndex{7}\)

Solution

Theorem \(\PageIndex{3}\)

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

Example \(\PageIndex{8}\)

Solution

Theorem \(\PageIndex{4}\)

The Chinese Remainder Theorem

Theorem \(\PageIndex{6}\): Chinese Remainder Theorem

Note

Example \(\PageIndex{6}\)