4.5: Linear Congruences
- Page ID
- 25469
\( \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
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\).
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)\).
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 ) \).
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
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.
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).\)
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.
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\)
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\).
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\) |
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}.\)