Divisibility and Congruence

Divisibility is the fundamental relation of number theory. We say $a$ divides $b$ ($a \mid b$) if there exists an integer $k$ such that $b = ak$.

1. The Division Algorithm

For any integers $a$ and $b$ (with $b > 0$), there exist unique integers $q$ (quotient) and $r$ (remainder) such that: $a = bq + r, \quad 0 \le r < b$

def division_demo(a, b):
  q = a // b
  r = a % b
  print(f"{a} = {b} * {q} + {r}")
  return q, r

division_demo(103, 7)

2. Congruence Relations

Gauss introduced the notation $a \equiv b \pmod{n}$ to signify that $a$ and $b$ have the same remainder when divided by $n$. This is an equivalence relation, meaning it is reflexive, symmetric, and transitive.

Properties of Congruence:

1. If $a \equiv b$ and $c \equiv d$, then $a + c \equiv b + d \pmod{n}$.
2. If $a \equiv b$ and $c \equiv d$, then $ac \equiv bd \pmod{n}$.
3. $a^k \equiv b^k \pmod{n}$ for any $k \ge 0$.

3. Fast Modular Exponentiation

In cryptography, we often calculate $a^b \bmod n$ where $b$ is a massive number. We use the “Square and Multiply” algorithm to do this in logarithmic time.

def fast_pow(base, power, mod):
  result = 1
  while power > 0:
      if power % 2 == 1:
          result = (result * base) % mod
      base = (base * base) % mod
      power //= 2
  return result

# Calculate 7^100 mod 13
print(f"7^100 mod 13: {fast_pow(7, 100, 13)}")
# Compare with Python's built-in pow()
print(f"Verify with pow(7, 100, 13): {pow(7, 100, 13)}")

4. Fermat’s Little Theorem

If $p$ is prime and $a$ is not divisible by $p$, then $a^{p-1} \equiv 1 \pmod{p}$. This provides a fast way to check if a number is probably prime (the Fermat Primality Test).

5. Summary Check