Number Theory

Introduction to Number Theory

Number theory is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. Its origins stretch back to antiquity — the ancient Greeks, especially Euclid and Diophantus, investigated properties of numbers that continue to fascinate mathematicians today.

Carl Friedrich Gauss famously remarked, "Mathematics is the queen of the sciences, and number theory is the queen of mathematics." For centuries number theory was considered the purest of pure mathematics — beautiful but seemingly impractical. That changed dramatically in the late 20th century when number-theoretic ideas became the backbone of modern cryptography and computer security.

Number theory asks deceptively simple questions: Which numbers are prime? How are the primes distributed among the integers? Can every even number greater than 2 be written as the sum of two primes? These questions are easy to state, yet many remain unsolved to this day.

Major Areas of Number Theory

• Elementary number theory: Divisibility, primes, congruences — studied without advanced tools
• Analytic number theory: Uses calculus and complex analysis to study prime distribution
• Algebraic number theory: Extends integer concepts to algebraic number fields
• Computational number theory: Algorithms for primality testing, factoring, and cryptography
• Additive number theory: Representing integers as sums (e.g., Goldbach's Conjecture, Waring's Problem)

Natural Numbers and Integers

Number theory begins with the most fundamental objects in mathematics: the natural numbers ℕ = {1, 2, 3, 4, …} (some authors include 0) and the integers ℤ = {…, -3, -2, -1, 0, 1, 2, 3, …}.

The Peano Axioms

In the late 19th century, Giuseppe Peano formalized the natural numbers with a set of axioms that capture their essential structure:

1. Base element: 1 is a natural number (or 0, depending on convention).
2. Successor function: Every natural number n has a unique successor S(n), which is also a natural number.
3. No predecessor of base: There is no natural number whose successor is 1 (i.e., 1 is not the successor of any natural number).
4. Injectivity: If S(m) = S(n), then m = n (different numbers have different successors).
5. Axiom of Induction: If a property holds for 1, and whenever it holds for n it also holds for S(n), then the property holds for all natural numbers.

Mathematical Induction

Mathematical induction is the proof technique derived directly from the Peano axioms. To prove a statement P(n) for all natural numbers n ≥ 1:

1. Base case: Show P(1) is true.
2. Inductive step: Assume P(k) is true for some k ≥ 1 (inductive hypothesis), and prove that P(k + 1) follows.

The Well-Ordering Principle

The Well-Ordering Principle states that every non-empty subset of the natural numbers has a least element. Although this sounds obvious, it is logically equivalent to the Principle of Mathematical Induction and is a powerful proof tool.

Many fundamental results in number theory — including the existence of prime factorizations — rely on well-ordering. The typical proof strategy is proof by contradiction: assume a counterexample exists, then use well-ordering to find a minimal counterexample, and derive a contradiction.

Divisibility

Divisibility is the most basic concept in number theory. We say that an integer a divides an integer b if there exists an integer k such that b = a · k. We write a | b (read "a divides b").

Basic Properties of Divisibility

For integers a, b, c:

• Reflexivity: a | a for every nonzero integer a (since a = a · 1)
• Transitivity: If a | b and b | c, then a | c
• Linearity: If a | b and a | c, then a | (bx + cy) for any integers x, y
• Comparison: If a | b with a, b > 0, then a ≤ b
• Multiplication: If a | b, then a | (b · c) for any integer c
• Sign: a | b if and only if (-a) | b if and only if a | (-b)

The Division Algorithm

The Division Algorithm is a cornerstone of number theory. Despite its name, it is a theorem, not an algorithm.

Divisibility Rules

Quick tests to determine whether a number is divisible by small primes:

• By 2: Last digit is even (0, 2, 4, 6, 8)
• By 3: Sum of digits is divisible by 3
• By 4: Last two digits form a number divisible by 4
• By 5: Last digit is 0 or 5
• By 6: Divisible by both 2 and 3
• By 7: Double the last digit and subtract from the rest; repeat until testable
• By 8: Last three digits form a number divisible by 8
• By 9: Sum of digits is divisible by 9
• By 11: Alternating sum of digits is divisible by 11

Prime Numbers

A prime number is an integer greater than 1 whose only positive divisors are 1 and itself. An integer greater than 1 that is not prime is called composite.

The first few primes are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, …

Euclid's Theorem: Infinitude of Primes

One of the most elegant proofs in all of mathematics, dating back over 2,300 years:

The Fundamental Theorem of Arithmetic

This theorem establishes that primes are the "building blocks" of all integers:

The existence part is proved by strong induction; the uniqueness part uses a key property of primes called Euclid's Lemma: if a prime p divides a product ab, then p | a or p | b.

The Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient and efficient algorithm for finding all primes up to a given limit N:

1. Write down all integers from 2 to N.
2. Start with the smallest unmarked number (2). Circle it — it's prime.
3. Cross out all multiples of 2 (4, 6, 8, 10, …).
4. Move to the next unmarked number (3). Circle it — it's prime.
5. Cross out all multiples of 3 (9, 15, 21, …) that haven't been crossed out already.
6. Continue this process. You only need to sieve up to √N.
7. All remaining unmarked numbers are prime.

Distribution of Primes

Although primes become less frequent among larger numbers, they never "run out." The Prime Number Theorem, proved independently by Hadamard and de la Vallée Poussin in 1896, describes their asymptotic distribution:

Here π(x) denotes the number of primes less than or equal to x. Informally, the "probability" that a randomly chosen number near x is prime is approximately 1/ln(x).

• π(10) = 4 (primes: 2, 3, 5, 7)
• π(100) = 25
• π(1,000) = 168
• π(1,000,000) = 78,498
• π(1,000,000,000) = 50,847,534

Twin Primes

Twin primes are pairs of primes that differ by exactly 2. Examples include (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), and (71, 73).

The Twin Prime Conjecture asserts that there are infinitely many twin prime pairs. Despite intensive effort, this remains unproven. In 2013, Yitang Zhang made a breakthrough by proving that there are infinitely many pairs of primes differing by at most 70 million — a bound later reduced to 246 by the Polymath project.

Other Famous Conjectures

• Goldbach's Conjecture (1742): Every even integer greater than 2 is the sum of two primes. Verified up to 4 × 10¹⁸ but unproven.
• Legendre's Conjecture: There is always a prime between n² and (n + 1)² for every positive integer n.
• Mersenne Primes: Primes of the form 2ⁿ - 1 (e.g., 3, 7, 31, 127). It is unknown whether infinitely many exist.

Greatest Common Divisor and LCM

The greatest common divisor (GCD) of two integers a and b (not both zero) is the largest positive integer that divides both a and b. We write gcd(a, b).

The least common multiple (LCM) of two positive integers a and b is the smallest positive integer that is divisible by both a and b. We write lcm(a, b).

GCD and LCM from Prime Factorizations

If a = p₁^α₁ · p₂^α₂ · … · pₖ^αₖ and b = p₁^β₁ · p₂^β₂ · … · pₖ^βₖ (using all primes from both factorizations, with zero exponents where needed), then:

Key Identity

This elegant relationship connects the GCD and LCM. Using the example above: 36 · 7,560 = 272,160 = 360 · 756. ✓

The Euclidean Algorithm

The Euclidean Algorithm is one of the oldest and most important algorithms in mathematics (dating to ~300 BCE). It computes gcd(a, b) efficiently without needing prime factorizations, using the key property:

Repeatedly apply this until the remainder is 0. The last nonzero remainder is the GCD.

The Extended Euclidean Algorithm

The Extended Euclidean Algorithm not only computes gcd(a, b) but also finds integers x and y such that:

This is crucial for solving linear congruences and in the RSA cryptosystem.

Modular Arithmetic

Modular arithmetic is the arithmetic of remainders. Introduced systematically by Gauss in Disquisitiones Arithmeticae (1801), it is one of the most powerful concepts in number theory and has vast applications in computer science, cryptography, and pure mathematics.

Congruences

We say that a is congruent to b modulo m (written a ≡ b (mod m)) if m divides the difference a - b:

Properties of Congruences

Congruence modulo m is an equivalence relation (reflexive, symmetric, transitive) and is compatible with addition and multiplication:

• Addition: If a ≡ b (mod m) and c ≡ d (mod m), then a + c ≡ b + d (mod m)
• Subtraction: If a ≡ b (mod m) and c ≡ d (mod m), then a - c ≡ b - d (mod m)
• Multiplication: If a ≡ b (mod m) and c ≡ d (mod m), then ac ≡ bd (mod m)
• Exponentiation: If a ≡ b (mod m), then aⁿ ≡ bⁿ (mod m) for any positive integer n

Residue Classes

The integers modulo m fall into m distinct residue classes: {0, 1, 2, …, m - 1}. This set, denoted ℤ/mℤ (or ℤₘ), forms a ring under addition and multiplication modulo m.

Modular Inverses

An integer a has a multiplicative inverse modulo m — an integer a⁻¹ such that a · a⁻¹ ≡ 1 (mod m) — if and only if gcd(a, m) = 1. We find it using the Extended Euclidean Algorithm.

Solving Linear Congruences

A linear congruence ax ≡ b (mod m) has a solution if and only if gcd(a, m) | b. If d = gcd(a, m) divides b, there are exactly d incongruent solutions modulo m.

Fermat's Little Theorem and Euler's Theorem

Fermat's Little Theorem

One of the most important results in number theory, stated by Pierre de Fermat in 1640:

An equivalent formulation that works for all integers a (including multiples of p):

Euler's Totient Function

Euler's totient function φ(n) counts the number of integers from 1 to n that are coprime to n:

Computing φ(n)

• If p is prime: φ(p) = p - 1 (all integers 1 through p - 1 are coprime to p)
• If p is prime: φ(pᵏ) = pᵏ - pᵏ⁻¹ = pᵏ(1 - 1/p)
• Multiplicativity: If gcd(m, n) = 1, then φ(mn) = φ(m) · φ(n)
• General formula: For n = p₁^a₁ · p₂^a₂ · … · pₖ^aₖ:

Euler's Theorem

Euler's Theorem generalizes Fermat's Little Theorem from primes to all positive integers:

When n = p is prime, φ(p) = p - 1, so this reduces to Fermat's Little Theorem.

Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) is a result about simultaneous congruences that dates back to the 3rd century Chinese mathematician Sun Tzu (Sunzi). It says that a system of congruences with pairwise coprime moduli has a unique solution.

Constructive Solution

To find the solution explicitly:

1. Compute M = m₁ · m₂ · … · mₖ.
2. For each i, compute Mᵢ = M / mᵢ.
3. For each i, find yᵢ such that Mᵢ · yᵢ ≡ 1 (mod mᵢ) (the modular inverse of Mᵢ mod mᵢ).
4. The solution is x ≡ a₁M₁y₁ + a₂M₂y₂ + … + aₖMₖyₖ (mod M).

Diophantine Equations

Diophantine equations are polynomial equations where we seek integer solutions. They are named after Diophantus of Alexandria (c. 200–284 CE), who studied them extensively. Unlike ordinary algebra — where solutions can be any real or complex number — Diophantine equations restrict solutions to integers, making them much harder to analyze.

Linear Diophantine Equations

The simplest type is the linear Diophantine equation in two variables:

Existence of solutions: The equation ax + by = c has integer solutions if and only if gcd(a, b) | c.

Finding all solutions: If (x₀, y₀) is one particular solution, then all solutions are:

Famous Diophantine Equations

Pythagorean Equation: x² + y² = z²

Integer solutions are called Pythagorean triples. The complete parametric solution for primitive Pythagorean triples (where gcd(x, y, z) = 1) is:

where m > n > 0, gcd(m, n) = 1, and m - n is odd.

Fermat's Last Theorem: xⁿ + yⁿ = zⁿ

Pierre de Fermat conjectured in 1637 that the equation xⁿ + yⁿ = zⁿ has no positive integer solutions for n ≥ 3. He famously wrote that he had "a truly marvelous proof that this margin is too narrow to contain."

This conjecture stood unsolved for 358 years until Andrew Wiles proved it in 1995, in one of the greatest mathematical achievements of the 20th century. The proof uses deep ideas from algebraic geometry and modular forms, far beyond elementary number theory.

Pell's Equation: x² - Dy² = 1

For a positive non-square integer D, Pell's equation always has infinitely many solutions. The fundamental solution can be found using continued fractions.

Applications in Cryptography

Modern cryptography relies heavily on number theory. The security of many encryption systems depends on the computational difficulty of certain number-theoretic problems — particularly integer factorization and the discrete logarithm problem.

One-Way Functions

A one-way function is easy to compute in one direction but computationally infeasible to reverse. Number theory provides natural one-way functions:

• Multiplication vs. Factoring: Multiplying two large primes p · q is trivial; factoring the product N = pq back into p and q is extremely hard for large N.
• Modular exponentiation vs. Discrete logarithm: Computing aˣ mod n is fast (via repeated squaring); recovering x from aˣ mod n is very hard.

The RSA Cryptosystem

The RSA algorithm, invented by Rivest, Shamir, and Adleman in 1977, is one of the first and most widely used public-key cryptosystems. It rests entirely on results from number theory: Euler's Theorem, modular inverses, and the difficulty of factoring large numbers.

Key Generation

1. Choose two large distinct primes p and q (in practice, each 1024+ bits).
2. Compute n = p · q. This is the modulus.
3. Compute φ(n) = (p - 1)(q - 1). (Euler's totient of n.)
4. Choose an integer e with 1 < e < φ(n) and gcd(e, φ(n)) = 1. This is the public exponent. (A common choice is e = 65537.)
5. Compute d ≡ e⁻¹ (mod φ(n)) using the Extended Euclidean Algorithm. This is the private exponent.

Encryption and Decryption

where M is the plaintext message (as a number less than n) and C is the ciphertext.

Why Decryption Works

By construction, e · d ≡ 1 (mod φ(n)), so e · d = 1 + k · φ(n) for some integer k. Then:

The crucial step uses Euler's Theorem: M^φ(n) ≡ 1 (mod n) when gcd(M, n) = 1.

Security of RSA

RSA's security rests on the assumption that factoring n = pq is computationally infeasible when p and q are sufficiently large. If an attacker could factor n, they could compute φ(n) = (p - 1)(q - 1) and then recover the private key d. Current RSA implementations use keys of 2048 bits or more.

Other Number-Theoretic Cryptosystems

• Diffie-Hellman Key Exchange: Based on the difficulty of the discrete logarithm problem in modular arithmetic.
• ElGamal Encryption: Also based on discrete logarithms.
• Elliptic Curve Cryptography (ECC): Uses the group structure of elliptic curves over finite fields, achieving strong security with shorter keys than RSA.
• Primality Testing: The Miller-Rabin and AKS algorithms, rooted in number theory, are essential for generating the large primes RSA requires.