Number Theory Home

## Basic Properties of Congruences

The concept of congruence was introduced in the book Disquisitiones Arithmeticae ("Arithmetical Investigations" in Latin) written by 21 years old Carl Friedrich Gauss in 1798.

Given a positive integer $$n$$, integers $$a$$ and $$b$$ are congruent modulo $$n$$ if their difference is an integer multiple of $$n$$. We denote it by $$a\equiv b \:\left(\mathrm{mod}\: n \right)$$ (Read as $$a$$ is congruent to $$b$$ modulo $$n$$ ). $a \equiv b \:\left(\mathrm{mod}\: n\right) \iff n \vert (a-b) \iff a=kn+b \text{ for some } k\in \mathbb Z.$ Example. $$7 \equiv 1 \:\left(\mathrm{mod}\:3\right)$$ and $$9 \not\equiv 1 \:\left(\mathrm{mod}\:3\right)$$, i.e., $$9$$ and $$1$$ are incongruent modulo $$3$$.

Many arithmetic properties and operations on congruence are similar to that of equality as follows.

Proposition. Let $$n$$ be a positive integer. The following hold for all integers $$a,b,c$$, and $$d$$.

1. $$a \equiv a \:\left(\mathrm{mod}\: n\right)$$ (Reflexivity).
2. $$a \equiv b \:\left(\mathrm{mod}\:n \right) \iff b \equiv a \:\left(\mathrm{mod}\: n\right)$$ (Symmetry).
3. If $$a \equiv b \:\left(\mathrm{mod}\: n \right)$$ and $$b \equiv c \:\left(\mathrm{mod}\: n\right)$$, then $$a \equiv c \:\left(\mathrm{mod}\: n \right)$$ (Transitivity).
4. If $$a \equiv b \:\left(\mathrm{mod}\: n \right)$$, then $$a+c \equiv b+c \:\left(\mathrm{mod}\: n \right)$$ (Translation).
5. If $$a \equiv b \:\left(\mathrm{mod}\: n\right)$$, then $$ac \equiv bc \:\left(\mathrm{mod}\: n \right)$$ (Scaling).
6. If $$a \equiv b \:\left(\mathrm{mod}\: n\right)$$ and $$c \equiv d \:\left(\mathrm{mod}\: n \right)$$, then $$a+c \equiv b+d \:\left(\mathrm{mod}\: n \right)$$ (Addition).
7. If $$a \equiv b \:\left(\mathrm{mod}\: n\right)$$ and $$c \equiv d \:\left(\mathrm{mod}\: n \right)$$, then $$ac \equiv bd \:\left(\mathrm{mod}\: n \right)$$ (Multiplication).
8. If $$a \equiv b \:\left(\mathrm{mod}\: n\right)$$, then $$a^k \equiv b^k \:\left(\mathrm{mod}\: n \right)$$ for all nonnegative integers $$k$$ (Exponentiation).

Proof. (1) and (2) are obvious. For (3), suppose $$a \equiv b \:\left(\mathrm{mod}\: n \right)$$ and $$b \equiv c \:\left(\mathrm{mod}\: n \right)$$. Then $$a-b=rn$$ and $$b-c=sn$$ for some integers $$r$$ and $$s$$. Then $a-c=(a-b)+(b-c)=rn+sn=(r+s)n$ which means $$a \equiv c \:\left(\mathrm{mod}\: n \right)$$.

(4) and (5) are easy. For (6) and (7), suppose $$a \equiv b \:\left(\mathrm{mod}\: n \right)$$ and $$c \equiv d \:\left(\mathrm{mod}\: n \right)$$. Then $$a-b=xn$$ and $$c-d=yn$$ for some integers $$x$$ and $$y$$. Then $(a+c)-(b+d)=(a-b)+(c-d)=xn+yn=(x+y)n$ which means $$a+c \equiv b+d \:\left(\mathrm{mod}\: n \right)$$. For (7), note that $$a=b+xn$$ and $$c=d+yn$$. Then $ac=(b+xn)(d+yn)=bd+(by+xd+xyn)n$ which means $$ac \equiv bd \:\left(\mathrm{mod}\: n \right)$$. (8) holds by inductively using $$c=a$$ and $$d=b$$ in (7). ◼

Let us use the above properties for the following divisibility problem.

Problem. Determine if $$10$$ divides $$17^{23}-3$$.
It suffices to determine if $$17^{23}\equiv 3 \:\left(\mathrm{mod}\:{10} \right)$$. Note that $$17\equiv 7\:\left(\mathrm{mod}\:{10} \right)$$. Then $$17^2\equiv 7^2\equiv 9\:\left(\mathrm{mod}\: 10 \right)$$, $$17^3\equiv 9\cdot 17\equiv 3\:\left(\mathrm{mod}\: 10 \right)$$, and $$17^4\equiv 9^2\equiv 1\:\left(\mathrm{mod}\: 10 \right)$$ by (8) and (5). Now since $$23=4\cdot 5+3$$, $$17^{23}=(17^4)^5 17^3\equiv (1)^5 17^3\equiv 3 \:\left(\mathrm{mod}\: 10 \right)$$ by (8) and (5).

Note that while the converse of (4) is true, but not the converse of (5). For example, $$6\cdot 3 \equiv 2\cdot 3 \:\left(\mathrm{mod}\: 6\right)$$ but $$6 \not\equiv 2 \:\left(\mathrm{mod}\: 6\right)$$. How to divide both sides of a congruence?

Theorem. Let $$n$$ be a positive integer. Let $$a,b$$, and $$c$$ be integers. If $$ac \equiv bc \:\left(\mathrm{mod}\: n \right)$$, then $$a \equiv b \:\left(\mathrm{mod}\:\frac{n}{\gcd(n,c)} \right)$$.

Proof. Suppose $$ac \equiv bc \:\left(\mathrm{mod}\: n \right)$$. Then $$(a-b)c=ac-bc=kn$$ for some integer $$k$$. Dividing both sides by $$d=\gcd(n,c)$$, we get $(a-b)\frac{c}{d}=k\frac{n}{d}.$ So $$\frac{n}{d} \vert (a-b)\frac{c}{d}$$. Since $$\gcd(\frac{n}{d},\frac{c}{d})=1$$, $$\frac{n}{d} \vert (a-b)$$. ◼

Corollary. Let $$n$$ be a positive integer. The following hold for all integers $$a,b$$, and $$c$$.

1. If $$ac \equiv bc \:\left(\mathrm{mod}\: n \right)$$ and $$\gcd(c,n)=1$$, then $$a \equiv b \:\left(\mathrm{mod}\: n \right)$$.
2. If $$ac \equiv bc \:\left(\mathrm{mod}\: n \right)$$ for a prime $$n\nmid c$$, then $$a \equiv b \:\left(\mathrm{mod}\: n \right)$$.

Application. A nice application of modular arithmetic finds $$w$$, the day of the week, where $$w=0$$ means Sunday,..., $$w=6$$ means Saturday: For the date $$d/m/100c+y,\; c\geq 16,\; 0\leq y\leq 99$$, $w\equiv d+\left\lfloor 2.6m-0.2\right\rfloor-2c+y+\left\lfloor \frac{c}{4}\right\rfloor+\left\lfloor \frac{y}{4}\right\rfloor \:\left(\mathrm{mod}\: 7\right),$ where $$m=1$$ means March,..., $$m=12$$ means February. For $$4$$th of November, $$2024$$ we have $w\equiv 4+\left\lfloor 2.6\cdot 9-0.2\right\rfloor-2\cdot 20+24+\left\lfloor \frac{20}{4}\right\rfloor+\left\lfloor \frac{24}{4} \right\rfloor\equiv 22 \equiv 1 \:\left(\mathrm{mod}\: 7\right).$ So $$4$$th of November, $$2024$$ is a Monday.

Last edited