# Introduction to Congruences

:::info
**Definition (Congruence)**
Let $a,b$ be integers and $m$ be a positive integer. We say that $a$ is congruent to $b$ modulo $m$, written as $a \equiv b \pmod{m}$, if $m$ divides the difference $a−b$.
$$
a \equiv b \pmod{m} \iff m \mid (a-b)
$$
:::

:::warning
**Example**
1. $22 \equiv 4 \pmod{9}$ because $9 \mid (22-4)=18$.
2. $3 \equiv -6 \pmod{9}$ because $9 \mid (3-(-6))=9$.
3. $13 \not\equiv 5 \pmod{9}$ because $9 \nmid (13-5)=8$.
:::

## The Congruence Relation
Congruence modulo $m$ is an **equivalence relation**, which means it behaves similarly to standard equality. This is why we can work with congruences much like we work with equations.

:::danger
**Theorem**
Let $a, b$, and $m$ be integers with $m>0$. Then $a \equiv b \pmod{m}$ if and only if there exists an integer $k$ such that $a=b+km$.
:::

:::warning
**Example**
$19 \equiv -2 \pmod{7}$ because we can write $19 = -2 + 3\cdot 7$.
:::

### Properties of Congruence
Congruence modulo $m$ is an equivalence relation because it is:

* **Reflexive:** $a \equiv a \pmod{m}$
* **Symmetric:** $a \equiv b \pmod{m} \Rightarrow b \equiv a \pmod{m}$
* **Transitive:** $a \equiv b \pmod{m}, \; b \equiv c \pmod{m} \Rightarrow a \equiv c \pmod{m}$

:::info
**Definition (Residue and Residue Classes)**
A **residue modulo $m$** is an equivalence class defined as:
$$
[a] = \{ x \in \mathbb{Z} \mid x \equiv a \pmod{m} \} = \{ km+a \mid k \in \mathbb{Z} \}
$$

The congruence $a \equiv b \pmod{m}$ is equivalent to the statement $[a]=[b]$.
:::

:::info
**Definition (Complete System of Residues)**
A complete system of residues modulo $m$ is a set of integers such that every integer is congruent modulo $m$ to exactly one integer in the set.
:::

For example, by the division algorithm, any integer $a$ can be written as $a=qm+r$ where $0 \leq r < m$. Thus, $a \equiv b \pmod{m}$, and the set $\{0,1,\dots,m−1\}$ is a complete system of residues modulo $m$.

:::warning
**Example**
1. For $m=2$: $\mathbb{Z} = [0]\cup [1]$
* $[0]=\{2k \mid k\in \mathbb{Z}\}$ = even integers
* $[1]=\{2k+1 \mid k\in \mathbb{Z}\}$ = odd integers
2. For $m=3$: $\mathbb{Z}=[0]\cup[1]\cup[2]$
* $[0]=\{3k \mid k\in \mathbb{Z}\}$
* $[1]=\{3k+1 \mid k\in \mathbb{Z}\}$
* $[2]=\{3k+2 \mid k\in \mathbb{Z}\}$
:::

## Operations with Congruences
:::danger
**Theorem (Congruence Arithmetic)**
If $a \equiv b \pmod{m}$ and $c \equiv d \pmod{m}$, then:

1. $a+c \equiv b+d \pmod{m}$
2. $a-c \equiv b-d \pmod{m}$
3. $ac \equiv bd \pmod{m}$
:::

:::warning
**Example**
Given $13 \equiv 3 \pmod{5}$ and $7 \equiv 2 \pmod{5}$:
* **Addition:** $20=13+7 \equiv 3+2=5 \equiv 0 \pmod{5}$.
* **Subtraction:** $6=13-7 \equiv 3-2=1 \pmod{5}$.
* **Multiplication**: $91=13\cdot 7 \equiv 3\cdot 2=6 \equiv 1 \pmod{5}$
:::

:::danger
**Corollary (Exponentiation)**
If $a \equiv b \pmod{m}$ and $k$ is a positive integer, then $a^k \equiv b^k \pmod{m}$.
:::

:::warning
**Example**
$$
49^2 \equiv 4^2 = 16 \equiv 1 \pmod{5}
$$
:::

## Key Theorems on Congruences
:::danger
**Theorem (Cancellation)**
If $ac \equiv bc \pmod{m}$ and $d = \mathrm{gcd}(c,m)$, then
$$a \equiv b \pmod{\tfrac{m}{d}}.$$
:::

:::warning
**Example**
1. $50 \equiv 20 \pmod{15}$.
* Here $c=10$ and $m=15$, so $d= \textrm{gcd}(10,15)=5$.
* Therefore, we can cancel the factor of $10$ and reduce the modulus: $5 \equiv 2 \pmod{3}$.
2. $42 \equiv 7 \pmod{5}$.
* Here $c=7$ and $m=5$, so $d= \textrm{gcd}(7,5)=1$.
* Therefore, we can cancel the factor of 7 without changing the modulus: $6 \equiv 1 \pmod{5}$.
:::

:::danger
**Theorem (Linear Transformation of Residue Systems)**
If $\{r_1,\dots,r_m\}$ is a complete system of residues modulo $m$ and a is a positive integer with $\textrm{gcd}(a,m)=1$, then the set
$$
\{ar_1+b, ar_2+b, \dots, ar_m+b\}
$$

is also a complete system of residues modulo $m$.
:::

:::danger
**Theorem**
If $a \equiv b \pmod{m_i}$ for $i=1 \dots k$, then
$$
a \equiv b \pmod{ \textrm{lcm}(m_1,\ldots,m_k)}.
$$
:::

:::success
**Exercise**
1. Show that each of the following congruences holds.
* a) $13 \equiv 1 \pmod{2}$
* b) $22 \equiv 7 \pmod{5}$
* c) $91 \equiv 0 \pmod{13}$
* d) $69 \equiv 62 \pmod{7}$
* e) $-2 \equiv 1 \pmod{3}$
* f) $-3 \equiv 30 \pmod{11}$
* g) $111 \equiv -9 \pmod{40}$
* h) $666 \equiv 0 \pmod{37}$
2. For which positive integers $m$ is each of the following statements true?
* a) $27 \equiv 5 \pmod{m}$
* b) $1000 \equiv 1 \pmod{m}$
* c) $1331 \equiv 0 \pmod{m}$
3. Show that if $a$ is an odd integer, then
$a^2 \equiv 1 \pmod{8}$.
4. Find the least nonnegative residue modulo 28 of each of the following integers.
* a) $99$
* b) $1100$
* c) $12,345$
* d) $-1$
* e) $-1000$
* f) $-54,321$
5. Find the least positive residue of $1! + 2! + 3! + \cdots + 100!$ modulo each of the following integers.
* a) $2$
* b) $7$
* c) $12$
* d) $25$
6. Show that if $a, b,$ and $m$ are integers with $m > 0$ and $a \bmod m = b \bmod m$, then $a \equiv b \pmod{m}$.
7. Construct a table for subtraction modulo $6$.
8. What time does a 12-hour clock read
* a) $29$ hours after it reads $11$ o’clock?
* b) $100$ hours after it reads $2$ o’clock?
* c) $50$ hours before it reads $6$ o’clock?
9. Show that if $n$ is an odd positive integer, then $$1 + 2 + 3 + \cdots + (n-1) \equiv 0 \pmod{n}.$$ Is this statement true if $n$ is even?
10. Show by mathematical induction that if $n$ is a positive integer, then $$5^n \equiv 1 + 4n \pmod{16}.$$
:::