Number Theory
Reference · Always free
Explore divisibility, primes, modular arithmetic, the Euclidean algorithm, and cryptographic applications.
Concepts in this topic
- Divisibility & Primes — Study divisibility rules, prime numbers, and the Fundamental Theorem of Arithmetic
- Modular Arithmetic — Learn clock arithmetic and congruence relations
- GCD & Euclidean Algorithm — Compute greatest common divisors efficiently
- Applications — Apply number theory to cryptography and other areas
Key formulas & identities
| Name | Formula | Meaning |
|---|---|---|
| Division Algorithm | a = d × q + r, where d > 0 and 0 ≤ r < d | Any integer a divided by positive d gives a unique quotient q and remainder r |
| GCD-LCM Relationship | gcd(a, b) × lcm(a, b) = |a × b| | The product of the GCD and LCM equals the absolute product of the numbers |
| Euclidean Algorithm | gcd(a, b) = gcd(b, a mod b) | The GCD can be computed by repeatedly taking remainders |
| Bézout's Identity | ∃ x, y ∈ ℤ : a × x + b × y = gcd(a, b) | The GCD of two integers can always be expressed as their integer linear combination |
| Fermat's Little Theorem | aᵖ⁻¹ ≡ 1 (mod p) when p is prime and p ∤ a | For prime p, raising a to the (p-1) power gives 1 modulo p |
| Euler's Theorem | aᵠ⁽ⁿ⁾ ≡ 1 (mod n) when gcd(a, n) = 1 | Generalizes Fermat's Little Theorem to any modulus using Euler's totient |
| Euler's Totient (Prime Power) | φ(pᵏ) = pᵏ - pᵏ⁻¹ = pᵏ(1 - 1/p) | Euler's totient function for a power of a prime |
| Euler's Totient (Product) | φ(a × b) = φ(a) × φ(b) when gcd(a, b) = 1 | Euler's totient is multiplicative for coprime arguments |