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 unknown.
The congruence holds exactly when \(n\mid(ax-b). \)
A solution is an integer \(x\) that satisfies the congruence.
In this section, we will use \(n\geq2\). Since in Modulo \(1\), every integer belongs to the same residue class.
Check whether \(x=4\) solves \(3x\equiv 5 \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 \(5x \equiv 3 \pmod {11} \), between \(0\) and \(10\) inclusive.
Solution
Possible solutions are \( 0, 1,2, \ldots, 10\).
Test the residue classes \(0, 1, 2, 3, 4, 5, 6, 7, 8, 9\):
\(\begin{array}{c|ccccc}
x & 0 & 1 & 2 & 3 & 4 &5& 6& 7& 8,&9 &10\\
\hline
5x & 0 & 5 & 10 & 15 & 20&25&30&35&40&45&50\\ \hline
5x\pmod {11} & 0 & 5 & 10 & 4 & 9&3&8&2&7&1&6\end{array}\)
The only solution is \(5\).
Example \(\PageIndex{3}\):
Solve \(3x \equiv 1\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 \equiv 2\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\). Since \( 2(1)\equiv2\pmod4,\qquad 2(3)\equiv2\pmod4, \)the solutions are \(1\) and \(3\).
Method II: Simplifying Congruences via Divisibility Properties
Theorem \(\PageIndex{1}\):Cancellation theorem
Let \(n \in \mathbb{Z}_+\) and \(a,b, c\in \mathbb{Z}\). If \(\gcd(c,n)=1\) and \(ac \equiv bc \pmod{n}\) then \(a \equiv b \pmod{n}\)
- Proof
-
Let \(n \in \mathbb{Z}_+\) and \(a,b, c\in \mathbb{Z}\). Assume that \(\gcd(c,n)=1\) and \(ac \equiv bc \pmod{n}\). Since \(ac \equiv bc \pmod{n}\), there exists an integer \(m\in \mathbb{Z}\) such that \(ac-bc=mn.\) Thus \((a-b)c=mn\). Thus \(n \mid (a-b)c\). Since \(\gcd(c,n)=1\), Euclid's lemma gives \(n \mid (a-b)\). Hence, \(a \equiv b \pmod{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\), by the cancellation theorem \(x \equiv 3 \pmod{8}\).
Let \(n \in \mathbb{Z}_+\) and \(a,b, c\in \mathbb{Z}\). Then \(ac \equiv bc \pmod{n}\) if and only if \(a \equiv b \left(mod\, \dfrac{n}{\gcd(c,n)}\right).\)
- Proof
-
Let \(n \in \mathbb{Z}_+\) and \(a,b, c\in \mathbb{Z}\). Let \(d=\gcd(c,n)\). The there exist integers \(c_1,n_1\in \mathbb{Z}\) such that \( c=dc_1, n=dn_1, \) where \(\gcd(c_1,n_1)=1\). Then
\(\begin{aligned} ac\equiv bc\pmod n &\iff n\mid c(a-b)\\ &\iff dn_1\mid dc_1(a-b)\\ &\iff n_1\mid c_1(a-b)\\ &\iff n_1\mid(a-b)\\ &\iff a\equiv b\pmod{n_1}. \end{aligned} \)
Thus
\( \boxed{ac\equiv bc\pmod n \iff a\equiv b\pmod{\dfrac{n}{d}}.} \)
The proof remains valid when \(c=0\), using the usual convention \(\gcd(0,n)=n\).
Solve \(9x \equiv 6 ( mod \,24 ) \).
Solution
Since \(d=\gcd(9,24)=3\) and \(3\mid6\),
\( 9x\equiv6\pmod{24} \iff3x\equiv2\pmod8. \)
Because \(3^{-1}\equiv3\pmod8\),
\( x\equiv3(2)\equiv6\pmod8. \)
Consequently, the three incongruent solutions modulo \(24\) are
\( \boxed{x\equiv6,14,22\pmod{24}.} \)
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)\).
When \(d\mid b\), let \(x_0\) be any particular solution. Then the complete set of integer solutions is
\[ \boxed{ \left\{x_0+k\frac nd:k\in\mathbb Z\right\}. } \]
The \(d\) distinct solution classes modulo \(n\) are
\[ \boxed{ x\equiv x_0+k\frac nd\pmod n, \qquad k=0,1,\ldots,d-1. } \]
- Proof
-
Let \(n \in \mathbb{Z}^+\) and \(a, b \in \mathbb{Z}\) with \(a \neq 0\). The linear congruence \(ax \equiv b \pmod{n}\) is equivalent to the equation (called the Diophantine equation) \(ax-ny=b,\) where \(y\in \mathbb{Z}\).
By Bézout's identity, this equation has an integer solution if and only if \(\gcd(a,n)\mid b\).
Assume \(d\mid b\), and set
\( a'= \dfrac{a}{d},\quad b'=\dfrac{b}{d},\quad n'=\dfrac{n}{d} \)
Then
\( ax\equiv b\pmod n \iff a'x\equiv b'\pmod{n'}. \)
Since \(\gcd(a',n')=1\), the reduced congruence has a unique solution modulo \(n'\), say \(x_0\).
Thus every integer solution satisfies
\( x=x_0+kn',\qquad k\in\mathbb Z. \])
Two such solutions are congruent modulo \(n=dn'\) if and only if their corresponding \(k\) values are congruent modulo \(d\). Hence there are exactly \(d\) incongruent solutions modulo \(n\).
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: \(\dfrac{a}{d}x \equiv \dfrac{b}{d} \pmod{\dfrac{n}{d}}\)
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 \(u\) and \(v\) such that \(au+nv=1.\) Then \(au \equiv 1 \pmod{n} \). Note that \(1\) is the multiplicative identity on \(\pmod{n}\). In this case, \(u (mod \,n) \) is the inverse of \(a (mod \,n)\). Thus \( a^{-1}\equiv u\pmod 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
\(7x\equiv5\pmod{26}.\)
Solution
Since \(\gcd(7,26)=1\), an inverse exists. From \( \begin{aligned}26&=3(7)+5\\, 7 &=5+2\\, 5&=2(2)+1\end{aligned}\), back-substitution gives \(1=3(26)-11(7)\), so \(7^{-1}\equiv-11\equiv15\). Multiply the congruence by \(15\):
\[x\equiv15(5)=75\equiv23\pmod{26}.\]
Verify: \(7(23)-5=156=6(26)\).
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\pmod{n}\) and \( x \equiv b(mod\, m)\). Moreover \(x\) is unique modulo \(mn\).
- Proof
-
Let \(a, b \in \mathbb{Z}\) and \(n,m \in \mathbb{N}\) such that \(\gcd(n,m) = 1\). Write \(x=a+nt\). Substitution into the second congruence gives
\(nt\equiv b-a\pmod m. \)
Since \(\gcd(n,m)=1\), \(n\) has an inverse modulo \(m\), so
\( t\equiv n^{-1}(b-a)\pmod m. \)
This determines \(t\) uniquely modulo \(m\), and therefore determines \(x\) uniquely 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, 14, 17 \ldots \).
Since \(x \equiv 3 (mod\, 5)\), the possible solutions are \(3, 8, 13, \ldots\).
Then \(x\equiv8\pmod{15}\). 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\).
- Proof
-
Let
\( M=\prod_{i=1}^{k}m_i,\qquad M_i=M/m_i. \)
Because the moduli are pairwise coprime,
\(\gcd(M_i,m_i)=1. \)
Choose \(u_i\in\mathbb Z\) such that
\( M_iu_i\equiv1\pmod{m_i}. \)
Then
\( \boxed{x=\sum_{i=1}^{k}a_iM_iu_i} \)
satisfies all the congruences. Modulo \(m_j\), every term except the \(j\)-th is zero, and the remaining term is congruent to \(a_j\).
If \(x\) and \(y\) are two solutions, each \(m_i\) divides \(x-y\). Since the moduli are pairwise coprime, \(M\mid(x-y)\). Thus the solution is unique modulo \(M\).
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.
|
\(i\) |
\(a_i\) |
\(m_i\) |
\(M_i\) |
\(u_i=M_i^{-1}\pmod{m_i}\) |
|---|---|---|---|---|
|
1 |
3 |
5 |
56 |
1 |
|
2 |
1 |
7 |
40 |
3 |
|
3 |
6 |
8 |
35 |
3 |
Therefore,
\(\begin{aligned} x&\equiv3(56)(1)+1(40)(3)+6(35)(3)\\ &\equiv168+120+630\\ &\equiv918\\ &\equiv78\pmod{280}. \end{aligned} \)
Verification:
\(\begin{aligned} 78&\equiv3\pmod5,\\ 78&\equiv1\pmod7,\\ 78&\equiv6\pmod8. \end{aligned} \)
Hence
\( \boxed{x\equiv78\pmod{280}.} \)