Congruences modulo n: a ≡ b [n] if a and b share a remainder

Definition

$a$ is congruent to $b$ modulo $n$ if $a - b$ is divisible by $n$:

$a \equiv b \pmod{n} \iff n \mid (a - b)$

Equivalently: $a$ and $b$ have the same remainder in division by $n$.

Examples

• $17 \equiv 5 \pmod{12}$ (since $17 - 5 = 12$).
• $-3 \equiv 4 \pmod{7}$ (since $-3 - 4 = -7$).
• $25 \equiv 1 \pmod{24}$ (useful for clock time!).

Operations: preserved

If $a \equiv a' \pmod n$ and $b \equiv b' \pmod n$:

• Addition: $a + b \equiv a' + b' \pmod n$
• Subtraction: $a - b \equiv a' - b' \pmod n$
• Multiplication: $a \times b \equiv a' \times b' \pmod n$
• Power: $a^k \equiv (a')^k \pmod n$

⚠️ Division is not always possible!

Application 1: divisibility rule

To test if $n$ is divisible by $9$: sum of digits.

Why? Because $10 \equiv 1 \pmod 9$, so $10^k \equiv 1 \pmod 9$. A number is congruent to the sum of its digits mod 9.

Application 2: huge remainder

Compute $2^{100}$ mod 5.

$2^4 = 16 \equiv 1 \pmod 5$.

$100 = 4 \times 25$, so $2^{100} = (2^4)^{25} \equiv 1^{25} = 1 \pmod 5$.

Remainder = 1.

Application 3: day of week

Today = Wednesday. In 100 days?

$100 = 14 \times 7 + 2$, so $100 \equiv 2 \pmod 7$. Wednesday + 2 = Friday.

Fermat’s little theorem

If $p$ is prime and $a$ not divisible by $p$:

$a^{p - 1} \equiv 1 \pmod p$

Use: simplify powers modulo a prime.

Common mistakes

1. Dividing in a congruence without $\gcd = 1$ with $n$.
2. Writing $a \equiv b \pmod n$ when $a - b$ isn’t divisible by $n$.
3. Forgetting remainders are non-negative ($0 \leq r < n$).

?À toi de jouer

46 mod 7 = ?

A.4B.6C.7D.0

Valider