Divisibility and Primes - Main Theorem

The Fundamental Theorem of Arithmetic stands as one of the most important results in all of mathematics. It guarantees that every integer has a unique factorization into primes, providing the foundation for much of algebraic number theory and abstract algebra.

TheoremFundamental Theorem of Arithmetic

Every integer $n > 1$ can be expressed as a product of prime numbers: $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ where $p_1 < p_2 < \cdots < p_k$ are distinct primes and $a_i \geq 1$ for all $i$ .

Moreover, this factorization is unique up to the order of the factors.

The theorem consists of two parts: existence and uniqueness. Existence is relatively straightforward to prove by strong induction, but uniqueness requires the crucial property that if a prime divides a product, it must divide one of the factors.

ExamplePrime Factorizations

Consider several examples of prime factorization:

$60 = 2^2 \cdot 3 \cdot 5$
$1001 = 7 \cdot 11 \cdot 13$
$2310 = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11$ (primorial of 11)

The uniqueness guarantee means that $60$ cannot be written as $2^3 \cdot 5$ or any other combination of primes with different exponents.

Remark

The Fundamental Theorem of Arithmetic fails in some natural generalizations. For instance, in the ring $\mathbb{Z}[\sqrt{-5}]$ , we have: $6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5})$

Both factorizations are into irreducible elements, but the factorization is not unique. This motivates the study of unique factorization domains in abstract algebra.

TheoremEuclid's Lemma

Let $p$ be a prime number, and let $a, b \in \mathbb{Z}$ . If $p \mid ab$ , then $p \mid a$ or $p \mid b$ .

More generally, if $p \mid a_1 a_2 \cdots a_n$ , then $p \mid a_i$ for some $i \in \{1, 2, \ldots, n\}$ .

Euclid's Lemma is the key property that distinguishes primes from general irreducible elements. It is essential for proving the uniqueness part of the Fundamental Theorem of Arithmetic.

ExampleApplying Euclid's Lemma

Suppose $7 \mid (15 \cdot 22)$ . Since $7$ is prime, Euclid's Lemma tells us that $7 \mid 15$ or $7 \mid 22$ .

Indeed, $15 = 7 \cdot 2 + 1$ , so $7 \nmid 15$ . Therefore, we must have $7 \mid 22$ , which is false since $22 = 7 \cdot 3 + 1$ .

Actually, $15 \cdot 22 = 330 = 7 \cdot 47 + 1$ , so $7 \nmid 330$ . The premise was false, making the implication vacuously true.

Let's try again: $5 \mid (15 \cdot 22) = 330$ . Then $5 \mid 15$ (true: $15 = 3 \cdot 5$ ) or $5 \mid 22$ (false). The lemma holds.

The Fundamental Theorem allows us to express gcd and lcm in terms of prime factorizations, providing an alternative computational method when factorizations are known.