Number Theory & Modular Arithmetic

Divisibility and remainders

• Modular inverse exists iff gcd(a,m)=1.
• RSA preview: multiply large primes; invert exponents mod φ(n).
• Chinese Remainder Theorem: unique solution mod mn when moduli coprime.