Modular arithmetic essentials
For olympiad problems, reduce early and track remainders.
- Fermat's little theorem: if p is prime and gcd(a,p)=1, then a^(p−1) ≡ 1 (mod p).
- Chinese remainder: combine congruences when moduli are coprime.
- Euclid's lemma: if p|ab and p is prime, then p|a or p|b.