4.5: Linear Congruences
- Page ID
- 25469
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 \(4\).
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 (mod\, \dfrac{m}{\gcd(c,m)})\)
- 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)\}=\{x_0, x_0+\dfrac{m}{d}, x_0+\dfrac{2m}{d},\ldots, x_0+\dfrac{(d-1)m}{d}\}\), 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)\}=\{x_0, x_0+\dfrac{m}{d}, x_0+\dfrac{2m}{d},\ldots, x_0+\dfrac{(d-1)m}{d}\}\), 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_n \in \mathbb{Z}\) and \(m_1,\cdots, m_n \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{eqnarray*} x & \equiv a_1(mod\, m_1)\\ x &\equiv a_2(mod\, m_2)\\. &\\ .&\\x &\equiv a_n(mod\, m_n)\\ \end{eqnarray*}
Moreover \(x\) is unique modulo \(m_1\ldots m_n\).