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\).
\(a \equiv a \:\left(\mathrm{mod}\: n\right)\) (Reflexivity).
\(a \equiv b \:\left(\mathrm{mod}\:n \right) \iff b \equiv a \:\left(\mathrm{mod}\: n\right)\) (Symmetry).
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).
If \(a \equiv b \:\left(\mathrm{mod}\: n \right)\), then \(a+c \equiv b+c \:\left(\mathrm{mod}\: n \right)\) (Translation).
If \(a \equiv b \:\left(\mathrm{mod}\: n\right)\), then \(ac \equiv bc \:\left(\mathrm{mod}\: n \right)\) (Scaling).
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).
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).
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\).
If \(ac \equiv bc \:\left(\mathrm{mod}\: n \right)\) and \(\gcd(c,n)=1\), then \(a \equiv b \:\left(\mathrm{mod}\: n \right)\).
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.