5.2 Congruence of Integers

Class: CSE 16 Subject: computer-science discrete-math Date: 2024-11-06 Teacher: Prof. Musacchio

Contrapositive Proof

Congruent Modulo n

• Given integers $a$ and $b$ and $n\in \mathbb{N}$, we say that $a$ and $b$ are congruent modulo $n$ if $n|(a-b)$. We express this as $a\equiv b$ (mod n). If $a$ and $b$ are not congruent modulo $n$, we write this as $a\not\equiv b$ (mod n).

Examples

1. $9\equiv 1$ (mod 4) because $4|(9-1)$.
2. $6\equiv 10$ (mod 4) because $4|(6-10)$.
3. $146\equiv 8$ (mod 4) because $4-(14-8)$.

• In practical terms, a ≡ b (mod n) means that a and b have the same remainder when divided by n.

Example 1

• Proposition Let a, b ∈ Z and n ∈ N. If a ≡ b (mod n), then a2 ≡ b2 (mod n).
  • Proof. Suppose a ≡ b (mod n).
  • By definition of congruence of integers, this means n | (a − b).
  • Then by definition of divisibility, there is an integer c for which a − b = nc.
  • Now multiply both sides of this equation by a + b.
    • a − b = nc
    • (a − b)(a + b) = nc(a + b)
    • a2 − b2 = nc(a + b)
  • Since c(a + b) ∈ Z, the above equation tells us n | (a2 − b2).
  • According to Definition 5.1, this gives a2 ≡ b2 (mod n)