Euclid's Theorems — Definition, Formula & Examples

Euclid's theorems are a collection of foundational results attributed to the ancient Greek mathematician Euclid, most notably the proof that there are infinitely many prime numbers and the algorithm for finding the greatest common divisor of two integers.

Among the principal results: (1) The Infinitude of Primes — for any finite list of primes $p_1, p_2, \ldots, p_n$ , the number $p_1 p_2 \cdots p_n + 1$ is not divisible by any $p_i$ , so at least one additional prime must exist. (2) The Division Algorithm — for integers $a$ and $b > 0$ , there exist unique integers $q$ and $r$ with $a = bq + r$ and $0 \le r < b$ . (3) Euclid's Lemma — if a prime $p$ divides $ab$ , then $p \mid a$ or $p \mid b$ .

How It Works

The proof that primes are infinite works by contradiction. Assume only finitely many primes exist, multiply them all together, and add 1. The resulting number leaves remainder 1 when divided by every prime on the list, so it must have a prime factor not on the list — a contradiction. The Euclidean algorithm uses repeated division to find the GCD: divide the larger number by the smaller, replace the larger with the remainder, and repeat until the remainder is 0. The last nonzero remainder is the GCD.

Worked Example

Problem: Use the Euclidean algorithm to find GCD(252, 105).

Step 1: Divide 252 by 105.

252 = 105 \times 2 + 42

Step 2: Divide 105 by the remainder 42.

105 = 42 \times 2 + 21

Step 3: Divide 42 by the remainder 21.

42 = 21 \times 2 + 0

Answer: The last nonzero remainder is 21, so GCD(252, 105) = 21.

Why It Matters

Euclid's theorem on the infinitude of primes is a cornerstone of number theory and underpins modern cryptography, including RSA encryption. The Euclidean algorithm is one of the oldest known algorithms still in active use — it appears in computer science courses, competition math, and whenever you need to simplify fractions or solve modular equations.

Common Mistakes

Mistake: Assuming that

p_1 p_2 \cdots p_n + 1

is itself always prime.

Correction: The proof only guarantees this product-plus-one has a prime factor not already on the list. For example,

2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30031 = 59 \times 509

, which is composite.