Fundamental Theorem of Arithmetic

Existence of Prime Factorization

We have classified numbers into two categories: prime numbers and composite numbers. Primes numbers should be considered as the building blocks of all numbers, composite numbers are built from prime numbers by multiplying them together. We will formally state this as the following theorem:

Theorem

Every integer $n$ except $0$ and $\pm 1$ can be expressed as a product of prime numbers.

Proof of Theorem

It is sufficient to prove this theorem for positive integers. For a negative number, we can always write it as $-n$ where $n$ is a positive integer, then:

$$n=p_1{p}_2\cdots p_k\Rightarrow -n=(-p_1)p_2\cdots p_k,$$

where $-p_1$ is also a prime number under our definition.

We will use a proof by contradiction. Let $S$ be the set of positive integers that cannot be expressed as a product of prime numbers, and suppose $S$ is non-empty. By the well-ordering axiom, $S$ has a smallest element $m$. Clearly $m$ cannot be a prime number itself, so we can write $m=ab$ where $1<a,b<m$. By the minimality of $m$, both $a$ and $b$ can be expressed as a product of prime numbers:

$$a=p_1{p}_2\cdots p_k,b=q_1{q}_2\cdots q_l.$$

Therefore, $m=p_1{p}_2\cdots p_k{q}_1{q}_2\cdots q_l$ is also a product of prime numbers, which contradicts the assumption that $m$ is in $S$. This completes the proof. $■$

Uniqueness of Prime Factorization

Now suppose we have two different prime factorizations of an integer $n$:

$$n=p_1{p}_2\cdots p_k=q_1{q}_2\cdots q_l.$$

We need to show $k=l$ and the two factorizations are the same up to reordering and sign. We assume $k\ge l$ without loss of generality.

Then $p_1$ divides the right-hand side, so it must divide some $q_i$ by this property. Without loss of generality, we assume $p_1\mid q_1$. Now by this property of prime numbers, we have $p_1=\pm q_1$. We can cancel $p_1$ and $q_1$ from both sides and get:

$$\pm p_2\cdots p_k=q_2\cdots q_l.$$

We notice again $p_2$ divides the right-hand side, so it must divide some $q_i$. By the same argument, we have $p_2=\pm q_2$. We can continue this process and conclude $p_i=\pm q_i$ for all $1\le i\le l$. Now suppose $k>l$, then we will have left over primes $p_{l+1},p_{l+2},\dots ,p_k$ on the left-hand side, and we will get:

$$\pm p_{l+1}\cdots p_k=1,$$

but this is impossible since $|p_i|\ge 2$ for all $i$. Therefore, $k=l$ and the two factorizations are the same up to reordering and sign. $■$