📋 Prerequisites

• Modular Arithmetic Basics
• GCD & LCM

Now we go deeper into modular arithmetic: inverses (the modular version of division), Fermat's little theorem, Euler's theorem, Wilson's theorem, and fast exponentiation. These are the workhorses of competition number theory — they let you compute huge powers instantly and solve congruences like a pro.

📚 Key Concepts

Modular Inverse

The inverse of $a$ modulo $m$ is a number $a^{-1}$ such that:

\[ a \cdot a^{-1} \equiv 1 \pmod{m} \]

The inverse exists if and only if gcd(a, m) = 1 (a and m are coprime).

When it exists, it's unique mod m.

\(Example: 3 \\times 5 = 15 \\equiv 1 (mod 7), so the inverse of 3 mod 7 is 5.\)

How to Find Inverses

Method 1: Brute force (for small m) — \(try a \\times 1, a \\times 2, ... until you get 1 mod m.\)

Method 2: Extended Euclidean Algorithm — find integers x, y such that ax + my = 1. Then x mod m is the inverse.

Method 3: Fermat's Little Theorem (when m is prime) — see below.

Fermat's Little Theorem (FLT)

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

\[ a^{p-1} \equiv 1 \pmod{p} \]

Equivalently: $ a^p \equiv a \pmod{p} $ for any integer a.

Application to inverses: If p is prime and p ∤ a, then $ a^{-1} \equiv a^{p-2} \pmod{p} $.

Why: multiply both sides of $ a^{p-1} \equiv 1 $ by $ a^{-1} $ to get $ a^{p-2} \equiv a^{-1} $.

Application to exponents: $ a^k \equiv a^{k \bmod (p-1)} \pmod{p} $ (when a not divisible by p). Reduces huge exponents fast!

Euler's Totient Function φ(n)

φ(n) counts how many integers from 1 to n are coprime to n.

Formula: If $ n = p_1^{a_1} p_2^{a_2} ... p_k^{a_k} $:

\[ \varphi(n) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right)...\left(1 - \frac{1}{p_k}\right) \]

Examples:

• φ(7) = 6 (prime p: φ(p) = p-1)
• φ(12) = φ\(((2^{2} \\times 3) = 12 \\times (1-\\frac{1}{2}) \\times (1-\\frac{1}{3}) = 12 \\times \\frac{1}{2} \\times \\frac{2}{3}\) = 4\)
• φ(1) = 1 (by convention)

Euler's Theorem

If gcd(a, n) = 1:

\[ a^{\varphi(n)} \equiv 1 \pmod{n} \]

This is the generalization of Fermat's Little Theorem to composite moduli.

FLT is the special case where n is prime (φ(p) = p-1).

Application: $ a^k \equiv a^{k \bmod \varphi(n)} \pmod{n} $ when gcd(a,n) = 1. Reduces exponents modulo φ(n).

Wilson's Theorem

An integer $p > 1$ is prime if and only if:

\[ (p-1)! \equiv -1 \pmod{p} \]

\(Example: p = 5. (5-1)! = 4! = 24 \\equiv 24 - 25 = -1 (mod 5).\) ✓

Useful for theoretical proofs and some competition problems about factorials mod primes.

Fast Exponentiation (Binary Exponentiation)

Compute $ a^n \pmod{m} $ in O(log n) multiplications instead of O(n).

Idea: Break the exponent into powers of 2.

Example: $ a^{13} = a^8 \times a^4 \times a^1 $ (since 13 = 8 + 4 + 1 = \(1101_{2})\)

Algorithm:

1. result = 1, base = a mod m
2. While exponent > 0:
   • \(If exponent is odd: result = (result \\times base) mod m\)
   • \(base = (base \\times base) mod m\)
   • exponent = exponent // 2

Chinese Remainder Theorem (Preview)

If moduli are pairwise coprime, a system of congruences has a unique solution modulo their product.

We'll cover this in detail in the CRT module.

✏️ Example Problems