Skip to main content
Mathematics LibreTexts

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

    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 \(4\).

    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 (mod\, \dfrac{m}{\gcd(c,m)})\)

    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)\}=\{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).\)

    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

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

    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{1}\)

    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}.\)


    This page titled 4.5: Linear Congruences is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Pamini Thangarajah.

    • Was this article helpful?