Unique Prime Factorization

Statement of the Theorem

The fundamental theorem of arithmetic states that every integer $n>1$ can be written as a product of prime numbers, and that this product is unique up to the order of the factors.

Thus every integer $n>1$ has a representation

n=p_1p_2\cdots p_k,

where each $p_i$ is prime.

The same factorization is often written by grouping equal primes:

n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r},

where

p_1<p_2<\cdots<p_r

are distinct primes and

\alpha_i\ge1.

For example,

360=2^3\cdot3^2\cdot5.

This means that the multiplicative structure of $360$ is completely determined by the primes $2$ , $3$ , and $5$ , together with their exponents.

Existence of Factorization

We first prove that every integer $n>1$ can be written as a product of primes.

If $n$ is prime, then there is nothing to prove. It is already a product of one prime.

If $n$ is composite, then

n=ab

for some integers $a,b$ satisfying

1<a<n, \qquad 1<b<n.

If $a$ and $b$ are prime, then $n$ is a product of primes. If one of them is composite, factor it again. Since each factor is smaller than $n$ , this process cannot continue forever.

A formal proof uses strong induction. Assume every integer $m$ with

2\le m<n

has a prime factorization. If $n$ is composite, write

n=ab

with $1<a,b<n$ . By the induction hypothesis, both $a$ and $b$ have prime factorizations. Multiplying these factorizations gives a prime factorization of $n$ .

Thus every integer greater than $1$ has at least one prime factorization.

Euclid’s Lemma

The uniqueness part rests on Euclid’s lemma.

If $p$ is prime and

p\mid ab,

then

p\mid a

p\mid b.

To prove this, suppose

p\nmid a.

Since $p$ is prime, the only positive divisors of $p$ are $1$ and $p$ . Hence

\gcd(p,a)=1.

Because

p\mid ab

and $\gcd(p,a)=1$ , the coprimality result from the previous section gives

p\mid b.

Thus a prime dividing a product must divide one of the factors.

By repeated application, if

p\mid a_1a_2\cdots a_k,

then $p$ divides at least one factor $a_i$ .

Uniqueness of Factorization

Suppose an integer $n>1$ has two prime factorizations:

n=p_1p_2\cdots p_r

and

n=q_1q_2\cdots q_s,

where all $p_i$ and $q_j$ are prime.

Since

p_1\mid n,

we have

p_1\mid q_1q_2\cdots q_s.

By Euclid’s lemma, $p_1$ divides one of the primes $q_j$ . Since $q_j$ is prime, its only positive divisors are $1$ and $q_j$ . Therefore

p_1=q_j.

Cancel this common prime from both factorizations. Repeating the argument, every prime on the left matches one prime on the right.

Thus the two factorizations contain exactly the same primes with exactly the same multiplicities, possibly written in a different order.

This proves uniqueness.

Canonical Form

The uniqueness theorem allows each integer $n>1$ to be written in canonical form:

n=\prod_{i=1}^{r} p_i^{\alpha_i},

where the primes are distinct and ordered:

p_1<p_2<\cdots<p_r,

and the exponents are positive integers.

For example,

756=2^2\cdot3^3\cdot7.

This form is canonical because no choices remain once the primes are ordered increasingly.

Divisibility in Prime Exponents

Prime factorization turns divisibility into comparison of exponents.

Suppose

a=\prod p_i^{\alpha_i}

and

b=\prod p_i^{\beta_i},

where missing primes are assigned exponent $0$ . Then

a\mid b

if and only if

\alpha_i\le \beta_i

for every prime $p_i$ .

For example,

12=2^2\cdot3

and

180=2^2\cdot3^2\cdot5.

Since the exponent of $2$ in $12$ is at most that in $180$ , and the exponent of $3$ in $12$ is at most that in $180$ , we have

12\mid180.

GCD and LCM from Factorization

Prime factorization also gives compact formulas for greatest common divisors and least common multiples.

a=\prod p_i^{\alpha_i}

and

b=\prod p_i^{\beta_i},

then

\gcd(a,b)=\prod p_i^{\min(\alpha_i,\beta_i)}

and

\operatorname{lcm}(a,b)=\prod p_i^{\max(\alpha_i,\beta_i)}.

Thus the gcd takes common prime powers with smaller exponents, while the lcm takes all prime powers with larger exponents.

This gives another proof of the identity

\gcd(a,b)\operatorname{lcm}(a,b)=ab

for positive integers $a$ and $b$ .

Role in Number Theory

Unique prime factorization is the structural foundation of elementary number theory. It says that primes are the irreducible multiplicative components of the positive integers.

Many arithmetic questions become simpler after translating them into prime exponents. Divisibility, gcds, lcms, reduced fractions, divisor counts, and multiplicative functions all rely on this theorem.

The theorem also marks a boundary. In the ordinary integers, factorization into primes is unique. In more general rings, unique factorization may fail. Understanding that failure leads to ideals, Dedekind domains, class groups, and algebraic number theory.