Number Theory: The Queen of Mathematics

Primes and Fundamental Theorems

Prime numbers: integers greater than 1 divisible only by 1 and themselves — the "atoms" of arithmetic. Fundamental Theorem of Arithmetic: every integer >1 has a unique prime factorization (Euclid's Elements, ~300 BC). Euclid's proof of infinite primes: if finitely many primes p₁...pₙ, then p₁×p₂×...×pₙ + 1 is not divisible by any — contradiction. Prime Number Theorem (Hadamard, de la Vallée-Poussin, 1896): π(x) ~ x/ln(x) — primes thin out logarithmically but never disappear. Twin prime conjecture: infinitely many pairs (p, p+2)? Yitang Zhang (2013): proved bounded gaps between primes (initially 70 million, now reduced to 246 by Maynard/Tao). Goldbach's conjecture (1742): every even integer >2 is the sum of two primes — verified up to 4×10¹⁸ but unproven. Mersenne primes: 2ᵖ−1 — largest known primes. As of 2024: 2⁸²⁵⁸⁹⁹³³−1 (24,862,048 digits). GIMPS: distributed computing project finding Mersenne primes since 1996.

Modular Arithmetic and Congruences

Modular arithmetic: arithmetic on remainders. a ≡ b (mod n) means n divides (a−b). Clock arithmetic: 14:00 ≡ 2:00 (mod 12). Fermat's Little Theorem: aᵖ⁻¹ ≡ 1 (mod p) for prime p, gcd(a,p)=1 — basis of primality testing. Euler's theorem: generalizes Fermat to composite moduli using Euler's totient function φ(n). Chinese Remainder Theorem (CRT): system of congruences with coprime moduli has a unique solution — used in RSA optimization. Quadratic reciprocity (Gauss, "golden theorem"): determines which primes p have x² ≡ q (mod p) solvable — connects two seemingly unrelated primes. Primitive roots: generators of (Z/nZ)* — exist for primes, powers of primes, and 2p^k. Discrete logarithm problem: given g, h, n, find x such that gˣ ≡ h (mod n) — believed computationally hard, basis of Diffie-Hellman key exchange. Elliptic curves over finite fields: y² = x³ + ax + b (mod p) — rich algebraic structure, foundation of ECC (Elliptic Curve Cryptography).

The Riemann Hypothesis

Riemann zeta function: ζ(s) = Σ(1/nˢ) for Re(s) > 1, analytically continued to all complex s ≠ 1. Euler product: ζ(s) = Π(1−p⁻ˢ)⁻¹ over primes — connects zeta function to prime distribution. Trivial zeros: ζ(s) = 0 at s = −2, −4, −6, ... (negative even integers). Non-trivial zeros: all other zeros lie in the critical strip 0 < Re(s) < 1. Riemann Hypothesis (1859): all non-trivial zeros have Re(s) = 1/2 (lie on the "critical line"). Importance: RH implies the strongest possible error term in the Prime Number Theorem — primes are distributed as regularly as possible. Computational verification: first 10¹³+ zeros all lie on the critical line — but numerical evidence doesn't constitute proof. Millennium Prize Problem: one of seven Clay Mathematics Institute problems — $1 million prize. Generalized RH: extends to Dirichlet L-functions, Dedekind zeta functions — even broader implications. Consequences if true: better bounds for prime gaps, error terms in arithmetic progressions, connections to random matrix theory and quantum chaos. Hilbert: "If I were to awaken after having slept for a thousand years, my first question would be: has the Riemann Hypothesis been proved?"

Applications in Cryptography

RSA encryption (Rivest, Shamir, Adleman, 1977): security relies on the difficulty of factoring large numbers (product of two large primes). RSA key generation: choose primes p, q (~2048 bits each), compute n = pq, public exponent e, private exponent d ≡ e⁻¹ (mod φ(n)). Best factoring algorithm: General Number Field Sieve — sub-exponential but still infeasible for 2048-bit moduli with classical computers. Elliptic Curve Cryptography (ECC): equivalent security to RSA with much smaller keys (256-bit ECC ≈ 3072-bit RSA). Diffie-Hellman key exchange: first public key protocol (1976) — security based on discrete logarithm problem. Hash functions: SHA-256, SHA-3 — number-theoretic properties ensure collision resistance. Primality testing: Miller-Rabin (probabilistic), AKS (deterministic polynomial — 2002, proved PRIMES is in P). Post-quantum threat: Shor's algorithm factors integers in polynomial time on quantum computers — RSA and ECC will be broken. Post-quantum cryptography: lattice-based (CRYSTALS-Kyber), hash-based (SPHINCS+), code-based (Classic McEliece) — resist quantum attacks. Number theory: from Gauss's "queen of mathematics" — pure and beautiful — to the foundation of modern digital security.

❓ Frequently Asked Questions

Prime numbers: integers greater than 1 divisible only by 1 and themselves — the "atoms" of arithmetic. Fundamental Theorem of Arithmetic: every integer >1 has a unique prime factorization (Euclid's El...

Modular arithmetic: arithmetic on remainders. a ≡ b (mod n) means n divides (a−b). Clock arithmetic: 14:00 ≡ 2:00 (mod 12). Fermat's Little Theorem: aᵖ⁻¹ ≡ 1 (mod p) for prime p, gcd(a,p)=1 — basis of...

Riemann zeta function: ζ(s) = Σ(1/nˢ) for Re(s) > 1, analytically continued to all complex s ≠ 1. Euler product: ζ(s) = Π(1−p⁻ˢ)⁻¹ over primes — connects zeta function to prime distribution. Trivial z...

RSA encryption (Rivest, Shamir, Adleman, 1977): security relies on the difficulty of factoring large numbers (product of two large primes). RSA key generation: choose primes p, q (~2048 bits each), co...

Try it live

Everything above runs in your browser — open Spirograph and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.