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

2.1: Introduction to Congruences

  • Page ID
    28632
  • \( \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{\NN}{\mathbb N}\)
    \(\newcommand{\RR}{\mathbb R}\)
    \(\newcommand{\QQ}{\mathbb Q}\)
    \(\newcommand{\ZZ}{\mathbb Z}\)
    \(\newcommand{\Cc}{\mathcal C}\)
    \(\newcommand{\Dd}{\mathcal D}\)
    \(\newcommand{\Ee}{\mathcal E}\)
    \(\newcommand{\Ff}{\mathcal F}\)
    \(\newcommand{\Kk}{\mathcal K}\)
    \(\newcommand{\Mm}{\mathcal M}\)
    \(\newcommand{\Pp}{\mathcal P}\)
    \(\newcommand{\ind}{\operatorname{ind}}\)
    \(\newcommand{\ord}{\operatorname{ord}}\)

    As we mentioned in the introduction, the theory of congruences was developed by Gauss at the beginning of the nineteenth century.

    Definition

    Given \(a,b\in\ZZ\) and \(n\in\NN\), we say that \(a\) is congruent to \(b\) modulo \(n\) if \(n \mid (a-b)\), i.e., if \(\exists k\in\ZZ\) such that \(a=b+kn\). If \(a\) is congruent to \(b\) modulo \(n\), we write \(a\equiv b\pmod{n}\).

    Example \(\PageIndex{1}\)

    \(19\equiv 5\pmod7\). Similarly \(2k+1 \equiv 1\pmod2\) which means every odd number is congruent to 1 modulo 2.

    Congruence is much like equality in many ways. For example:

    Theorem \(\PageIndex{1}\)

    Given \(a,b,c,d\in\ZZ\) and \(n\in\NN\). Then

    1. If \(a\equiv b\pmod n\), then \(b\equiv a\pmod n\).
    2. If \(a\equiv b\pmod n\) and \(b\equiv c\pmod n\), then \(a\equiv c\pmod m\).
    3. If \(a\equiv b\pmod n\), then \(a+c \equiv b+c\pmod n\).
    4. If \(a\equiv b\pmod n\), then \(a-c \equiv b-c\pmod n\).
    5. If \(a\equiv b\pmod n\), then \(ac \equiv bc\pmod n\).
    6. If \(c>0\) and \(a\equiv b\pmod n\), then \(ac \equiv bc\pmod{nc}\).
    7. If \(a\equiv b\pmod n\) and \(c \equiv d\pmod n\) then \(a+c \equiv b+d\pmod n\).
    8. If \(a\equiv b\pmod n\) and \(c \equiv d\pmod n\) then \(a-c \equiv b-d\pmod n\).
    9. If \(a\equiv b\pmod n\) and \(c \equiv d\pmod n\) then \(ac \equiv bd\pmod n\).
    Proof
    1. If \(a \equiv b\pmod n\), then \(n\mid (a-b)\). Thus \(\exists k\in\ZZ\) such that \(a-b=kn\). This implies \(b-a=(-k)n\) and thus \(n\mid (b-a)\). Consequently \(b\equiv a\pmod n\).
    2. Since \(a\equiv b\pmod n\) and \(b\equiv c\pmod n\), \(n\mid (a-b)\) and \(n\mid (b-c)\). As a result, there \(\exists k,l\in\ZZ\) such that \(a=b+kn\) and \(b=c+ln\), which imply that \(a=c+(k+l)n\). In other words, \(a=c\pmod n\).
    3. Since \(a\equiv b\pmod n\), \(n \mid (a-b)\). So if we add and subtract \(c\) we get \[n\mid ((a+c)-(b+c))\] which means that \[a+c\equiv b+c\pmod n.\]
    4. Since \(a\equiv b\pmod n\), \(n \mid (a-b)\) so we can subtract and add \(c\) to get \[n\mid ((a-c)-(b-c))\] so \[a-c\equiv b-c\pmod n.\]
    5. If \(a \equiv b\pmod n\), \(n\mid (a-b)\). Thus there \(\exists k\in\ZZ\) such that \(a-b=kn\) and as a result \(ac-bc=(kc)n\). Therefore \[n\mid (ac-bc)\] and hence \[ac\equiv bc\pmod n.\]
    6. If \(a \equiv b\pmod n\), \(n\mid (a-b)\). Thus there \(\exists k\in\ZZ\) such that \(a-b=kn\) and as a result \[ac-bc=(k)cn.\] Thus \[nc\mid (ac-bc)\] and hence \[ac\equiv bc\pmod{nc}.\]
    7. Since \(a\equiv b\pmod n\) and \(c\equiv d\pmod n\), \(n\mid (a-b)\) and \(n\mid (c-d)\). As a result, there \(\exists k,l\in\ZZ\) such that \(a-b=kn\) and \(c-d=ln\). Note that \[(a-b)+(c-d)=(a+c)-(b+d)=(k+l)n.\] As a result, \[n\mid ((a+c)-(b+d)),\] hence \[a+c\equiv b+d\pmod n.\]
    8. If \(a=b+kn\) and \(c=d+ln\) for \(k,l\in\ZZ\), we have \[(a-b)-(c-d)=(a-c)-(b-d)=(k-l)n.\] As a result, \[n\mid ((a-c)-(b-d)),\] hence \[a-c\equiv b-d\pmod n.\]
    9. \(\exists k,l\in\ZZ\) such that such that \(a-b=kn\) and \(c-d=ln\) and thus \(ca-cb=(ck)n\) and \(bc-bd=(bl)n\). Note that \[(ca-cb)+(bc-bd)=ac-bd=(kc-lb)n.\] As a result, \[n\mid (ac-bd),\] hence \[ac\equiv bd\pmod n.\]Here is a technical result which will be useful later:

    Here is a technical result which will be useful later:

    Theorem \(\PageIndex{2}\)

    Given \(a,b,c\in\ZZ\), if \(a\mid c\), \(b\mid c\), and \(a\) and \(b\) are relatively prime, then \(ab\mid c\).

    Proof

    By Corollary 1.5.1, we know \(\exists m,n\in\ZZ\) such that \(ma+nb=1\). Also, because of the divisibility hypotheses, we also know \(\exists p,q\in\ZZ\) such that \(c=pa\) and \(c=qb\). Compute: \[c=c\cdot1=c(ma+nb)=mca+ncb=mqba+npab=(mq+np)ab\ .\] But this means \(ab\mid c\), as desired.

    Example \(\PageIndex{1}\)

    1. \(14\equiv 8\pmod6\) so \(8 \equiv 14\pmod6\).
    2. Because \(22\equiv 10\pmod6\) and \(10 \equiv 4\pmod6\), it is also true that \(22\equiv 4\pmod6\).
    3. \(50\equiv 20\pmod{15}\) so \(50+5=55\equiv 20+5=25\pmod{15}\).
    4. \(50\equiv 20\pmod{15}\) so \(50-5=45\equiv 20-5=15\pmod{15}\).
    5. \(19\equiv 16\pmod3\) so \(2(19)=38\equiv 2(16)=32\pmod3.\)
    6. \(19\equiv 16\pmod3\) so \(2(19)=38\equiv 2(16)=32\pmod{2\cdot3}\) or \(38\equiv 2(16)=32\pmod6.\)
    7. Because \(19\equiv 3\pmod8\) and \(17\equiv 9\pmod8\), we have \(19+17=36\equiv 3+9=12\pmod8\).
    8. Because \(19\equiv 3\pmod8\) and \(17\equiv 9\pmod8\), we have \(19-17=2\equiv 3-9=-6\pmod8\).
    9. Because \(19\equiv 3\pmod8\) and \(17\equiv 9\pmod8\), we have \(19(17)=323\equiv 3(9)=27\pmod8\).

    Here is a result which at first seems very simple, but turns out to be immensely useful – so useful it has a name.

    Lemma \(\PageIndex{1}\): Euclid's Lemma

    Given \(x,y,z\in\ZZ\), if \(x\mid yz\) and \(\gcd(x,y)=1\) then \(x\mid z\).

    Proof

    From Corollary 1.5.1, we know \(\exists m,n\in\ZZ\) such that \(mx+ny=1\). Multiplying by \(z\), we get \(mxz+nyz=z\). But we’ve assumed that \(x\mid yz\), so \(x\mid nyz\), and certainly \(x\mid mxz\), so \(x\mid mxz+nyz\), i.e., \(x\mid z\).

    We now present a theorem that will show one difference between equations and congruences: in equations, if we divide both sides of the equation by a non-zero number, equality holds. However, in congruences, this is not necessarily true. In other words, dividing both sides of a congruence by the same integer does not necessarily preserve the congruence.

    Theorem \(\PageIndex{3}\)

    1. Given \(a,b,c\in\ZZ\) and \(n\in\NN\), define \(d=\gcd(a,n)\in\NN\). If \(ab\equiv ac\pmod n\) then \(b\equiv c\pmod{n/d}\).
    2. In particular, if \(\gcd(a,n)=1\) then

      \[b=c\pmod n\qquad\Leftrightarrow\qquad ab\equiv ac\pmod n.\]

    Proof

    For Part 1, if \(ab\equiv ac\pmod n\), then \[n\mid (ab-ac)=a(b-c).\] Hence \(\exists k\in\ZZ\) such that \(a(b-c)=kn\). Dividing both sides by \(d\), we get \((a/d)(b-c)=k(n/d)\) or \((n/d)\mid (a/d)(b-c)\). Now, by Theorem 1.5.1 \(\gcd(a/d,n/d)=1\) so Euclid’s Lemma (Lemma 2.1.1) tells us that \((n/d) \mid (b-c)\). Hence \(b\equiv c\pmod{n/d}\).

    For Part 2, the direction \({}\Rightarrow{}\) is part 5 of Theorem 2.1.1, while \({}\Leftarrow{}\) is a special case of Part 1.

    Example \(\PageIndex{1}\)

    \(38 \equiv 10\pmod7\). Since \(\gcd(2,7)=1\), we have \(19\equiv 5\pmod7.\)

    One last technical result is worth stating clearly at this point:

    Theorem \(\PageIndex{4}\)

    Given \(n,d\in\NN\) such that \(d\mid n\), there are exactly \(d\) values \(x\in\ZZ\), up to congruence modulo \(n\), satisfying \(x\equiv 0\pmod{n/d}\).

    Proof

    Let \(x_j=j(n/d)\) for \(j=0,\dots,(d-1)\). Certainly each of these \(d\) values \(x_j\) is a multiple of \(n/d\) and so solves \(x\equiv 0\pmod{n/d}\). All we must show, then, is that every solution \(x\) of \(x\equiv 0\pmod{n/d}\) is congruent, modulo \(n\), to one of these \(x_j\).

    Let \(x\) be such a solution, so \(\exists k\in\ZZ\) such that \(x=k(n/d)\). Use the Division Algorithm for \(x\) divided by \(n\), getting \(x=qn+r\) for some \(q,r\in\ZZ\) with \(0\le r<n\). But \[r=x-qn=k(n/d)-qd(n/d)=(k-qd)(n/d)\] so \(r\) is a multiple of \((n/d)\) which lies in the range \([0,n)\). The only such multiples are the \(x_0,\dots,x_{(d-1)}\) defined above; say \(r=x_j\). Then \(x=qn+r=qn+x_j\equiv x_j\pmod{x_j}\), so every solution \(x\) is congruent modulo \(n\) to exactly one of the \(d\) particular solutions \(x_1,\dots,x_{(d-1)}\).

    Exercise \(\PageIndex{1}\)

    1. Determine whether \(3\) and \(99\) are congruent modulo \(7\) or not.
    2. Show that if \(x\) is an odd integer, then \(x^2\equiv 1\pmod8\).
    3. Show that if \(a,b\in\ZZ\) and \(m,n\in\NN\) are such that \(n \mid m\) and \(a\equiv b\pmod m\), then \(a\equiv b\pmod n\).
    4. Show that if \(n,k\in\NN\) and \(\{a_1,\dots,a_k,b_1,\dots,b_k\}\subset\ZZ\) satisfy \(a_i\equiv b_i\pmod n\) for \(i=1,2,...,k\), then \(\sum_{i=1}^ka_i\equiv\sum_{i=1}^kb_i\pmod n\).
    5. For which \(n\in\NN\) is it true that \(1+2+...+(n-1)\equiv 0\pmod n\)?
    • Was this article helpful?