Unique Factorization

A prime number is a positive integer greater than 1 whose only divisors are 1 and itself.

Theorem (Fundamental Theorem of Arithmetic). For every $n \in \mathbb{N}^+$ with $n > 1$, $n$ has a unique prime factorization. That is, we can write

$$n = p_1 p_2 \cdots p_k,$$

where $k \ge 1$, each $p_i$ is prime, and

$$p_1 \le p_2 \le \cdots \le p_k.$$

The proof relies on Euclid's Lemma.

Euclid's Lemma. If $p$ is prime and $p \mid ab$, then $p \mid a$ or $p \mid b$.

Corollary. If $p \mid q_1 q_2 \cdots q_\ell$, then $p \mid q_i$ for some $i \in [\ell]$.

Proof of Euclid's Lemma. Suppose $p$ is prime and $p \nmid a$. Then $\gcd(a, p) = 1$, so $a$ has a multiplicative inverse modulo $p$, denoted $a^{-1} \in \mathbb{F}_p$, with

If $p \mid ab$, then $ab \equiv 0 \pmod{p}$. Multiplying both sides by $a^{-1}$ gives

so $p \mid b$. A symmetric argument holds if $p \nmid b$. ∎

Proof of the Theorem. Suppose $n$ has two prime factorizations:

Then $p_1 \mid q_1 q_2 \cdots q_\ell$. By the corollary to Euclid’s Lemma, $p_1 \mid q_i$ for some $i$. Since both $p_1$ and $q_i$ are primes, we must have $p_1 = q_i$.

Canceling this common factor from both sides and applying induction to the remaining product yields that the two factorizations must agree up to order. Thus, prime factorization is unique. ∎

Corollary. Let

$$n = p_1^{d_1} p_2^{d_2} \cdots p_k^{d_k}, \quad m = q_1^{f_1} q_2^{f_2} \cdots q_\ell^{f_\ell},$$

where all $p_i$ and $q_j$ are distinct primes. If $n \mid m$, then for each $i \in [k]$, there exists some $j \in [\ell]$ such that

$$p_i = q_j, \quad d_i \le f_j.$$

Proof. Since $n \mid m$, every prime factor of $n$ must also divide $m$. Applying Euclid’s Lemma repeatedly and canceling common prime factors shows that the exponent of each $p_i$ in $n$ cannot exceed its exponent in $m$. This establishes the result. ∎