1.5: Linear Congruences
- Page ID
- 243463
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\dsum}{\displaystyle\sum\limits} \)
\( \newcommand{\dint}{\displaystyle\int\limits} \)
\( \newcommand{\dlim}{\displaystyle\lim\limits} \)
\( \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{\longvect}{\overrightarrow}\)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\ket}[1]{\left| #1 \right>}\)
\(\newcommand{\bra}[1]{\left< #1 \right|}\)
\(\newcommand{\braket}[2]{\left< #1 \vphantom{#2} \right| \left. #2 \vphantom{#1} \right>}\)
\(\newcommand{\braopket}[3]{\left< #1 \vphantom{#2}\vphantom{#3} \right| #2 \vphantom{#1}\vphantom{#3} \left| #3 \vphantom{#1}\vphantom{#2} \right>}\)
\(\newcommand{\qmvec}[1]{\mathbf{\vec{#1}}}\)
\(\newcommand{\op}[1]{\hat{\mathbf{#1}}}\)
\(\newcommand{\expect}[1]{\langle #1 \rangle}\)
\(\newcommand{\dfn}[1]{\emph{\textbf{#1}}}\)
Linear Congruences
A linear congruence in one variable is an equation of the form \( ax \equiv b \pmod{n} \), where \(n \in \mathbb{Z}_+\), \(a, b \in \mathbb{Z}\), and \(x \in \mathbb{Z}\) is an unknown variable.
A solution is an integer \(x\) that satisfies the congruence.
Check whether \(x=4\) solves \(3x\equiv5\pmod{7}.\)
Solution: Substituting \(x = 4\), we obtain \(3(4) = 12 \equiv 5 \pmod{7}\). Therefore, \(x = 4\) is a solution.
Solving a linear congruence means finding all integers \(x\) satisfying \(ax \equiv b \pmod{n}\). A congruence is said to be solvable if it has at least one integer solution. Although a solvable linear congruence has infinitely many integer solutions in \(\mathbb{Z}\), these solutions partition into a finite number of distinct residue classes modulo \(n\). Thus, there are at most \(n\) distinct solutions modulo \(n\), represented by the set \(\{0, 1, \dots, n-1\}\).
Throughout this section, we assume \(a \neq 0\).
Method I: Solve by Inspection (Exhaustive Testing)
Since any solution modulo \(n\) belongs to one of the \(n\) possible residue classes in \(\mathbb{Z}_n = \{0, 1, \dots, n-1\}\), we can find all solutions by systematically testing each value.
Example \(\PageIndex{2}\):
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{3}\):
Solve \(3x\equiv1\pmod{5}.\)
Solution:
Test the residue classes \(0,1,2,3,4\):
\(\begin{array}{c|ccccc}
x & 0 & 1 & 2 & 3 & 4\\
\hline
3x & 0 & 3 & 6 & 9 & 12\\ \hline
3x\pmod 5 & 0 & 3 & 1 & 4 & 2\end{array}\)
Thus, the unique solution modulo \(5\) is \(x\equiv2\pmod{5}.\)
Example \(\PageIndex{4}\):
Solve \(4x\equiv2\pmod{6}.\)
Solution:
Test \(x=0,1,2,3,4,5\):
\(
\begin{array}{c|cccccc}
x & 0&1&2&3&4&5\\
\hline
4x & 0&4&8&12&16&20\\ \hline
4x\pmod 6 & 0&4&2&0&4&2
\end{array}
\)
Therefore, there are two incongruent solutions modulo \(6\):
\(x \equiv 2 \pmod{6}\) and \(x \equiv 5 \pmod{6}\).
Find all solutions to \(3x \equiv 1 ( mod \,6 ) \), between \(0\) and \(5\) inclusive.
Solution
Possible solutions are \( 0, 1,2,3,4, 5\).
\begin{array}{c|cccccc}
x & 0&1&2&3&4&5\\
\hline
3x & 0&3&6&9&12&15\\ \hline
3x\pmod 6 & 0&3&0&3&0&3
\end{array}
\)
Since \(3x \bmod 6\) is never equal to \(1\), the congruence \(3x \equiv 1 \pmod{6}\) has no solutions.
Example \(\PageIndex{6}\):
Solve \(2x \equiv 2 ( mod \,4 ) \).
Solution
Possible solutions are \( 0, 1,2, 3\). The solutions are \(1\) and \(3\).
Method II: Simplifying Congruences via Divisibility Properties
Theorem \(\PageIndex{1}\)
Let \(n \in \mathbb{Z}_+\) and \(a,b, c\in \mathbb{Z}\). If \(\gcd(c,n)=1\) and \(ac \equiv bc (mod\, n)\) then \(a \equiv b (mod\, n)\)
- Proof
-
Let \(n \in \mathbb{Z}_+\) and \(a,b, c\in \mathbb{Z}\). Assume that \(\gcd(c,n)=1\) and \(ac \equiv bc (mod\, n)\). Since \(ac \equiv bc (mod\, n)\), \(ac-bc=mn,\) for \(n\in \mathbb{Z}.\) Thus \((a-b)c=mn\). Thus \(n \mid (a-b)c\). Since \(\gcd(c,n)=1\), \(n \mid (a-b)\). Hence, \(a \equiv b (mod\, n)\).
Solve \(3x \equiv 1 ( mod \,8 ) \).
Solution
Notice that \(1 \equiv 9 \pmod{8}\), so we rewrite the congruence as \(3x \equiv 9 \pmod{8}\).
Since \(\gcd(3, 8) = 1\), we can divide both sides by \(3\) to obtain \(x \equiv 3 \pmod{8}\).
Let \(n \in \mathbb{Z}_+\) and \(a,b, c\in \mathbb{Z}\). Then \(ac \equiv bc (mod\, n)\) if and only if \(a \equiv b \left(mod\, \dfrac{n}{\gcd(c,n)}\right)\)
Solve \(9x \equiv 6 ( mod \,24 ) \).
Solution
We rewrite this as \(3(3x) \equiv 3(2) \pmod{24}\). Since \(\gcd(3, 24) = 3\), applying the theorem gives:
\(3x \equiv 2 \pmod{8}\).
Rewriting \(2 \equiv 10 \equiv 18 \pmod{8}\), we obtain \(3x \equiv 18 \pmod{8}\). Dividing by \(3\) yields \(x \equiv 6 \pmod{8}\).
The above two methods are tedious when the numbers are large.
Method III: The Main Solvability Theorem & Modular Inverses
When moduli are large, inspection is inefficient. The following theorem provides a precise criterion for solvability.
Let \(n \in \mathbb{Z}^+\) and \(a, b \in \mathbb{Z}\) with \(a \neq 0\). The linear congruence \(ax \equiv b \pmod{n}\) has a solution if and only if \(d \mid b\), where \(d = \gcd(a, n)\).
Furthermore, if \(d \mid b\), then there are exactly \(d\) mutually incongruent solutions modulo \(n\). If \(x_0\) is a particular solution, the complete set of solutions modulo \(n\) is given by:
\[
x_k = x_0 + k \left(\frac{n}{d}\right) \pmod{n}, \quad \text{for } k \in \{0, 1, \dots, d - 1\}
\]
Hence the set of all mutually incongruent solutions modulo \(n\) is \[\{x \in \mathbb{Z} | x \equiv x_0(mod\, n)\}=\left\{x_0, x_0+\dfrac{n}{d}, x_0+\dfrac{2n}{d},\ldots, x_0+\dfrac{(d-1) n} {d} \right \}. \]
This theorem answers the following two questions about linear congruences:
1. Does a solution exist?
2. If it exists, how many mutually incongruent solutions are there modulo \(n\)?
How to Use the Solvability Theorem:
To solve \(ax\equiv b\pmod n,\) use the following checklist:
- Compute \(d=\gcd(a,n)\).
- Check whether \(d\mid b\).
- If \(d\nmid b\), there is no solution.
- If \(d\mid b\), there are exactly \(d\) incongruent solutions modulo \(n\).
- Divide \(a,b,n\) by \(d\), then solve the reduced congruence.
Solve \(6x\equiv5\pmod{9}.\)
Step 1: \(\gcd(6,9)=3.\)
Step 2: Check whether \(3 \mid 5\).
Since \(3 \nmid 5\), there is no solution.
Do not start by trying to divide by \(6\). First, check the gcd condition.
Solve
\(
5x\equiv3\pmod{7}.
\)
Solution
Since \(\gcd(5,7)=1\), there is exactly one solution modulo \(7\).
By inspection,
\(
5(2)=10\equiv3\pmod{7}.
\)
Therefore,
\(
\boxed{x\equiv2\pmod{7}}.
\)
Later we will solve this systematically using the inverse of \(5\) modulo \(7\).
We will see below how to find the solution for a particular case: using the multiplicative inverse modulo n
Let \(n \in \mathbb{Z}_+.\) Let \(a \in \mathbb{Z}\) such that \(a\) and \(n\) are relatively prime. Then there exist integers \(x\) and \(y\) such that \(ax+ny=1.\) Then \(ax \equiv 1 ( mod \,n) \). Note that \(1\) is the multiplicative identity on \(mod \,n\). In this case, \(x (mod \,n) \) is the inverse of \(a (mod \,n)\).
Theorem \(\PageIndex{4}\)
If \(\gcd(a,n)=1\) then \(ax \equiv b(mod \, n)\) has a unique solution \(x \equiv a^{-1}b(mod \, n).\) Thus, the set of all solutions is \(\{x \in \mathbb{Z} | x \equiv a^{-1}b(mod \, n)\}.\)
- Proof
-
Since \(\gcd(a,n)=1\), therefore \(a\) has an inverse \(a^{-1} \mod n\). Hence \(x \equiv a^{-1}b(mod \, n).\)
Solve
\(
6x\equiv9\pmod{15}.
\)
First,
\(
d=\gcd(6,15)=3.
\)
Since \(3\mid9\), solutions exist, and there are exactly \(3\) incongruent solutions modulo \(15\).
Divide by \(3\):
\(
2x\equiv3\pmod{5}.
\)
Since \(2^{-1}\equiv3\pmod{5}\),
\(
x\equiv3(3)=9\equiv4\pmod{5}.
\)
Hence, modulo \(15\),
\(
\boxed{x\equiv4,9,14\pmod{15}}.
\)
Why Did Three Solutions Appear?
From
\(
x\equiv4\pmod{5},
\)
we have
\(
x=4+5k.
\)
Modulo \(15\), choose \(k=0,1,2\):
\(
x=4,\ 9,\ 14.
\)
Then the pattern repeats.
Verification:
\(
6(4)=24\equiv9\pmod{15},
\)
\(
6(9)=54\equiv9\pmod{15},
\)
\(
6(14)=84\equiv9\pmod{15}.\)
Solve \(16x \equiv 11 ( mod \,35) \).
Solution
Step 1: Check Solvability
We first compute \(d = \gcd(16, 35)\) using the Euclidean Algorithm:
\begin{align*} 35 &= 2(16) + 3, \\ 16 &= 5(3) + 1, \\ 3 &= 3(1) + 0. \end{align*}
Since \(\gcd(16, 35) = 1\) and \(1 \mid 11\), a unique solution exists modulo \(35\).
Step 2: Find the Modular Inverse \(16^{-1} \pmod{35}\)
Working backward through the Euclidean Algorithm: \begin{align*} 1 &= 16 - 5(3) \\ &= 16 - 5(35 - 2 \cdot 16) \\ &= 16 - 5(35) + 10(16) \\ &= 11(16) - 5(35). \end{align*}
Taking this modulo \(35\) yields: \(11(16) \equiv 1 \pmod{35}\).
Hence, \(16^{-1} \equiv 11 \pmod{35}\).
Step 3: Solve for \(x\) \\
Multiply both sides of \(16x \equiv 11 \pmod{35}\) by the modular inverse \(11\): \begin{align*} x &\equiv 11 \cdot 11 \pmod{35} \\ &\equiv 121 \pmod{35}. \end{align*} Since \(121 = 3(35) + 16\), we reduce modulo \(35\): \(x \equiv 16 \pmod{35}\).
Solve \(17x \equiv 7 \pmod{43}\).
Solution
Since \(\gcd(17, 43) = 1\), a unique solution exists. We use the Extended Euclidean Algorithm to find \(17^{-1} \pmod{43}\):
Apply the Euclidean Algorithm:
\begin{align*}
43 &= 2(17)+9,\\
17 &= 1(9)+8,\\
9 &= 1(8)+1.
\end{align*}
Now work backward:
\begin{align*}
1 &= 9+(-1)8\\
&= 9+(-1)(17+(-1)9)\\
&= 2(9)+(-1)17\\
&= 2(43+(-2)(17))+(-1)17\\
&= 2(43)+(-5)(17).
\end{align*}
Thus,
\(
17(-5)\equiv1\pmod{43}.
\)
Hence,
\(17^{-1}\equiv-5\equiv38\pmod{43}.\)
Now, \(x \equiv (17)^{-1}7 ( mod \,43)\equiv (38)(7 )( mod \,43) \equiv 266 ( mod \,43) \equiv 8 ( mod \,43)\).
Solve
\(6x\equiv9\pmod{15}.\)
Solution
1. Compute \(d = \gcd(6, 15) = 3\).
2. Check divisibility: \(3 \mid 9\), so solutions exist, and there are exactly \(d = 3\) incongruent solutions modulo \(15\).
3. Divide the congruence by \(d = 3\):
\(2x \equiv 3 \pmod{5}\).
4. Solve the reduced congruence: since \(2^{-1} \equiv 3 \pmod{5}\), we have:
\(x \equiv 3(3) \equiv 4 \pmod{5}\).
5. Generate all \(3\) solutions modulo \(15\) by adding multiples of \(\frac{n}{d} = \frac{15}{3} = 5\):
\[
x \equiv 4, \; 4+5=9, \; 4+2(5)=14 \pmod{15}.
\]
The Chinese Remainder Theorem
In this section, we will explore how to solve simultaneous linear congruences. The Chinese Remainder Theorem (CRT) allows us to solve systems of simultaneous linear congruences with pairwise coprime moduli.
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{10}\):
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\).
Algorithm for Solving CRT Systems
Step 1: Calculate the product \(M = m_1 \times m_2 \times \ldots \times m_k\=\prod_{i=1}^k m_i\).
Step 2: Calculate the Modulus Factors. For each \(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\). That is for each \(i\), compute \(M_i^{-1} \pmod{m_i}\) such that \(M_i M_i^{-1} \equiv 1 \pmod{m_i}\).
Step 4: Combine Solutions. Finally, the solution \(x\) to the system of congruences is given by: \[ x \equiv \left( \sum_{i=1}^{k} a_i M_i M_i^{-1} \right) \pmod M \equiv \sum_{i=1}^k a_i M_i M_i^{-1} \pmod{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
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.
| \(a_i\) | \(m_i\) | \(M_i\) | \(M_i^{-1}\) | \(M\) |
| 3 | 5 | \(\dfrac{280}{5}=56\) | \(56 \equiv 1 \implies 1^{-1} \equiv 1\) | \(280\) |
| 1 | 7 | \(\dfrac{280}{7}=40\) | \(40 \equiv 5 \implies 5^{-1} \equiv 3\) | \(280\) |
| 6 | 8 | \(\dfrac{280}{8}=35\) | \(35 \equiv 3 \implies 3^{-1} \equiv 3\) | \(280\) |
Now, \(x \equiv ((3)(56)(1)+(7)(40(3)+(8)(35)(3)) \pmod{280} \equiv 918 \pmod{280} \equiv 78 \pmod{280}.\)