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