Skip to main content
\(\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}}\)
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}}\)

    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 a linear congruence has at most \(m\) solutions.

    Example \(\PageIndex{1}\)

    Solve \(x \equiv 6 ( mod \,11 ) \).

    Solution

    Possible solutions are \( 0, 1,2, \ldots, 10\). The only solution is \(6\).

    Example \(\PageIndex{2}\)

    Solve \(2x \equiv 3 ( mod \,7 ) \).

    Solution

    The only solution is \(5\).

    Example \(\PageIndex{3}\)

    Solve \(3x \equiv 1 ( mod \,8 ) \).

    Solution

    This congruence has no solution.

    Example \(\PageIndex{4}\)

    Solve \(2x \equiv 2 ( mod \,4 ) \).

    Solution

    The solutions are \(1\) and \(3\).

    The following theorems give a criterion for the solvability of \(ax \equiv b(mod \, m)\).

    Theorem \(\PageIndex{1}\)

    If \(\gcd(c,m)=1\) and \(ac \equiv bc (mod\, m)\) then \(a \equiv b (mod\, m)\)

    Proof

    Add proof here and it will automatically be hidden 

    Theorem \(\PageIndex{2}\)

    If \(\gcd(a,m)=1\) then \(ax \equiv b(mod \, m)\) has a unique solution.

    Proof

    Add proof here and it will automatically be hidden 

    Theorem \(\PageIndex{3}\)

    \(ax \equiv b(mod\, m)\) has a  solution if and only if \(\gcd(a,m) |b\).

    Proof

    Add proof here and it will automatically be hidden 

    The Chinese Remainder Theorem

    Theorem \(\PageIndex{4}\)

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

    Since \(x \equiv 3 (mod\, 5)\), the possible solutions are \(3, 8, 13,\). 

     Then \(x=8\). Since any \(y\) such that \(y \equiv 8 (mod\, 15)\) are also  solutions, we have \(23, 38, \cdots\)