Number Theory Summary

Discrete Math · Axiom Academy

Let's review how integer properties power modern cryptography and reveal deep mathematical patterns. Division Algorithm: For any integers a and b > 0, there exist unique q and r such that a = bq + r with 0 ≤ r Greatest Common Divisor: The largest positive integer that divides both a and b, denoted gcd(a, b) Euclidean Algorithm: Repeatedly apply division algorithm to find gcd efficiently: gcd(a, b) = gcd(b, r) where r is remainder Bézout's Identity: For any integers a and b, there exist integers x and y such that gcd(a, b) = ax + by Congruence Definition: a ≡ b (mod n) means n divides (a - b) , or equivalently, a and b have the same remainder when divided by n Arithmetic Properties: Congruences can be added, subtracted, and multiplied. Division requires the divisor to be coprime to the modulus Multiplicative Inverse: a has an inverse mod n if and only if gcd(a, n) = 1 . Find it using the extended Euclidean algorithm Chinese Remainder Theorem: Systems of congruences with coprime moduli have unique solutions modulo the product of moduli Definition: An integer p > 1 is prime if its only positive divisors are 1 and p itself Fundamental Theorem: Every integer greater than 1 can be uniquely factored into primes (up to order) Infinitude of Primes: There are infinitely many primes, proven by Euclid around 300 BCE Primality Testing: Trial division up to √n works but is slow. Fermat's test and Miller-Rabin provide efficient probabilistic methods

This is the written version of the interactive lesson above. See the full Discrete Math course.