Number Theory
Prime Checker
Prime Factorization
GCD (Euclidean Algorithm)
GCD as a Linear Combination
Finds x, y such that ax + by = gcd(a,b) (Bézout's identity), via the Extended Euclidean Algorithm. Works for zero, negative, and equal inputs.
LCM
Extended Euclidean Algorithm
Modular Inverse
Congruence Check
Chinese Remainder Theorem
Solve a system x ≡ ai (mod mi). Add as many congruences as you need. Supports both pairwise coprime moduli and non-coprime moduli (when a solution exists).
Euler's Totient φ(n)
Fermat's Little Theorem
Verifies ap-1 ≡ 1 (mod p) for prime p.
Euler's Theorem
Verifies aφ(n) ≡ 1 (mod n) for gcd(a,n)=1.
Understanding Number Theory
Number theory studies the properties of integers, especially divisibility, prime numbers, and the relationships between them. This module focuses on two of its most practically important tools: the greatest common divisor (via the Euclidean algorithm) and the Chinese Remainder Theorem, both of which sit at the heart of modern cryptography, including the RSA algorithm that secures much of the internet.
Key Definitions & Formulas
- GCD(a,b): the largest integer dividing both a and b, computed efficiently by repeated division (the Euclidean algorithm).
- Bézout's identity: for any a, b, there exist integers x, y such that ax + by = GCD(a,b) — a "linear combination" that the extended Euclidean algorithm finds directly.
- Coprime (relatively prime): two numbers whose GCD is 1.
- Chinese Remainder Theorem (CRT): given a system of congruences with pairwise coprime moduli, there's a unique solution modulo the product of the moduli.
- Modular arithmetic: arithmetic that "wraps around" after reaching a fixed modulus, written a ≡ b (mod n).
Worked Example
GCD(48, 18) via the Euclidean algorithm: 48 = 2×18 + 12, then 18 = 1×12 + 6, then 12 = 2×6 + 0, so GCD = 6. Working backwards through those steps (the extended algorithm) also expresses 6 as a linear combination: 6 = 1×18 - 1×12 = ... eventually 6 = (-1)×48 + 3×18, confirming ax + by = GCD directly.
Where This Is Used
- RSA and other public-key cryptography, built on GCD, coprimality, and modular arithmetic.
- Error-correcting codes and checksums.
- Hashing and pseudo-random number generation.
- Scheduling problems solved via the Chinese Remainder Theorem (e.g. recurring calendar events).