---
# System prepended metadata

title: Intro_congruence
tags: [Math312]

---

# 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}.$$
:::