Number Theory Explorer - Perfect, Abundant & Amicable Numbers

Key number theory concepts

• Prime numbers: integers greater than 1 divisible only by 1 and themselves. Every integer > 1 has a unique prime factorization (Fundamental Theorem of Arithmetic).
• GCD (Greatest Common Divisor): the largest integer that divides both a and b. Computed efficiently by the Euclidean algorithm: GCD(48, 18) = GCD(18, 12) = GCD(12, 6) = 6.
• LCM (Least Common Multiple): LCM(a, b) = (a × b) / GCD(a, b). Used for finding common denominators.
• Modular arithmetic: arithmetic on remainders. "Clock arithmetic" - 17 mod 12 = 5. Foundational to cryptography (RSA, Diffie-Hellman).

Goldbach's Conjecture

Every even integer greater than 2 can be expressed as the sum of two prime numbers. Verified computationally up to 4 × 10¹⁸, but never proved. One of the most famous unsolved problems in mathematics.

Euler's Totient Function

Euler's totient function φ(n) counts how many positive integers up to n are coprime with n (share no common factor other than 1). For example, φ(10) = 4 because 1, 3, 7, and 9 are coprime with 10.

The totient function is central to RSA encryption: the private key exponent d is calculated as the modular inverse of the public exponent e modulo φ(n), where n = p×q (product of two large primes). Specifically: e×d ≡ 1 (mod φ(n)).

Famous unsolved problems

• Goldbach's Conjecture (1742): every even integer > 2 is the sum of two primes. Verified up to 4×10¹⁸, never proved.
• Riemann Hypothesis (1859): all non-trivial zeros of the Riemann zeta function ζ(s) lie on the "critical line" Re(s) = ½. Its proof would unlock precise knowledge about the distribution of prime numbers. One of the Millennium Prize Problems ($1 million reward).
• Twin Prime Conjecture: there are infinitely many prime pairs (p, p+2), such as (11, 13), (17, 19), (41, 43). Yitang Zhang's 2013 breakthrough proved infinitely many prime pairs within a gap of 70 million - later reduced to 246.
• Collatz Conjecture: starting from any positive integer, repeatedly applying n/2 (if even) or 3n+1 (if odd) always eventually reaches 1. Verified for all numbers up to 2⁶⁸, but never proved.

Prime number theorem

Primes become less frequent as numbers get larger. The prime number theorem states that the number of primes up to x (denoted π(x)) is approximately x / ln(x). More precisely, π(x) ~ Li(x) where Li is the logarithmic integral.

In practical terms: among numbers near 1,000, about 1 in every ln(1000) ≈ 7 numbers is prime. Near 1,000,000 it is about 1 in 14. This explains why finding large primes for cryptography requires testing many candidates.