$$\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 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 2.1: Introduction to Congruences

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\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 \|}$$ $$\newcommand{\inner}{\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 \|}$$ $$\newcommand{\inner}{\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$$?