LearnMathOnline

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 (\mod n)$ (Read as $a$ is congruent to $b$ modulo $n$ ). $a \equiv b (\mod n) ⟺ n | (a - b) ⟺ a = k n + b for some k \in Z .$ Example. $7 \equiv 1 (\mod 3)$ and $9 ≢ 1 (\mod 3)$ , 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 (\mod n)$ (Reflexivity).
$a \equiv b (\mod n) ⟺ b \equiv a (\mod n)$ (Symmetry).
If $a \equiv b (\mod n)$ and $b \equiv c (\mod n)$ , then $a \equiv c (\mod n)$ (Transitivity).
If $a \equiv b (\mod n)$ , then $a + c \equiv b + c (\mod n)$ (Translation).
If $a \equiv b (\mod n)$ , then $a c \equiv b c (\mod n)$ (Scaling).
If $a \equiv b (\mod n)$ and $c \equiv d (\mod n)$ , then $a + c \equiv b + d (\mod n)$ (Addition).
If $a \equiv b (\mod n)$ and $c \equiv d (\mod n)$ , then $a c \equiv b d (\mod n)$ (Multiplication).
If $a \equiv b (\mod n)$ , then $a^{k} \equiv b^{k} (\mod n)$ for all nonnegative integers $k$ (Exponentiation).

Proof. (1) and (2) are obvious. For (3), suppose

a \equiv b (\mod n)

and

b \equiv c (\mod n)

. Then

a - b = r n

and

b - c = s n

for some integers

r

and

s

. Then

a - c = (a - b) + (b - c) = r n + s n = (r + s) n

which means

a \equiv c (\mod n)

.

(4) and (5) are easy. For (6) and (7), suppose

a \equiv b (\mod n)

and

c \equiv d (\mod n)

. Then

a - b = x n

and

c - d = y n

for some integers

x

and

y

. Then

(a + c) - (b + d) = (a - b) + (c - d) = x n + y n = (x + y) n

which means

a + c \equiv b + d (\mod n)

. For (7), note that

a = b + x n

and

c = d + y n

. Then

a c = (b + x n) (d + y n) = b d + (b y + x d + x y n) n

which means

a c \equiv b d (\mod n)

. (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 (\mod 10)$ . Note that $17 \equiv 7 (\mod 10)$ . Then $17^{2} \equiv 7^{2} \equiv 9 (\mod 10)$ , $17^{3} \equiv 9 \cdot 17 \equiv 3 (\mod 10)$ , and $17^{4} \equiv 9^{2} \equiv 1 (\mod 10)$ 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 (\mod 10)$ 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 (\mod 6)$ but $6 ≢ 2 (\mod 6)$ . How to divide both sides of a congruence?

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

Proof. Suppose

a c \equiv b c (\mod n)

. Then

(a - b) c = a c - b c = k n

for some integer

k

. Dividing both sides by

d = gcd (n, c)

, we get

(a - b) \frac{c}{d} = k \frac{n}{d} .

\frac{n}{d} | (a - b) \frac{c}{d}

. Since

gcd (\frac{n}{d}, \frac{c}{d}) = 1

\frac{n}{d} | (a - b)

. ◼

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

If $a c \equiv b c (\mod n)$ and $gcd (c, n) = 1$ , then $a \equiv b (\mod n)$ .
If $a c \equiv b c (\mod n)$ for a prime $n ∤ c$ , then $a \equiv b (\mod n)$ .

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 / 100 c + y, c \geq 16, 0 \leq y \leq 99$ , $w \equiv d + ⌊ 2.6 m - 0.2 ⌋ - 2 c + y + ⌊ \frac{c}{4} ⌋ + ⌊ \frac{y}{4} ⌋ (\mod 7),$ where $m = 1$ means March,..., $m = 12$ means February. For $4$ th of November, $2024$ we have $w \equiv 4 + ⌊ 2.6 \cdot 9 - 0.2 ⌋ - 2 \cdot 20 + 24 + ⌊ \frac{20}{4} ⌋ + ⌊ \frac{24}{4} ⌋ \equiv 22 \equiv 1 (\mod 7) .$ So $4$ th of November, $2024$ is a Monday.

Last edited 03/25/2022 22:47:29