Fundamental Theorem of Arithmetic

Any integer $ n > 1 $ can be factored as a product of a finite number $ k $ of distinct irreducible elements $ f_k $ (prime numbers), each raised to a positive exponent $ e_k > 0 $. Moreover, this factorization is unique: $$ n = f_1^{e_1} \cdot f_2^{e_2} \cdots f_k^{e_k} $$

The factorization of an integer is unique.

The only possible variation is the order in which the irreducible elements appear in the product.

Example

The number 36 can be factored into prime components as follows:

$$ \begin{array}{c|lcr} n & \text{d} & \\ \hline 36 & 2 \\ 18 & 2 \\ 9 & 3 \\ 3 & 3 \\ 1 \end{array} $$

So we can express the number as:

$$ 2^2 \cdot 3^2 $$

Both 2 and 3 are irreducible.

Proof

Existence of Factorization

Factorizing $ n = 2 $ is straightforward:

$$ 2 = 2^1 $$

By induction, assume that every integer $ k $ such that $ 2 \leq k < n $ has a valid factorization.

We need to show that $ n $ can also be factored.

If $ n $ is irreducible, then the factorization is simply $ n $ itself.
If $ n $ is reducible, it can be written as the product of two integers $ a $ and $ b $: $$ n = a \cdot b $$ where $ a, b $ are integers such that $ 2 \leq a, b < n $.
By the induction hypothesis, both $ a $ and $ b $ have valid factorizations.
Therefore, $ n $ must also have a factorization.

Thus, we have established the existence of a factorization for every positive integer $ n $.

Uniqueness of Factorization

Let $ m $ be the number of irreducible factors in the shortest possible factorization of an integer.

If $ m = 1 $, then the number itself must be irreducible (i.e., prime):

$$ p = p^1 $$

Suppose, for contradiction, that $ p $ has another factorization:

$$ p = q_1^{k_1} \cdot q_2^{k_2} \cdots q_n^{k_n} $$

where $ q_i $ are factors greater than 1, and $ k_i > 0 $.

Since $ p $ divides itself, it must also divide at least one of the factors $ q_x $ on the right-hand side.

If $ p $ is prime and divides $ q_x $, then $ q_x $ must be equal to $ p $:

$$ p \mid q_x \Rightarrow q_x = p $$

Rewriting the equation:

$$ p = q_x \cdot q_1^{k_1} \cdot q_2^{k_2} \cdots q_n^{k_n} $$

Since $ q_x = p $, the only way for this equality to hold is if all other exponents are zero:

$$ p = q_x \cdot q_1^{0} \cdot q_2^{0} \cdots q_n^{0} $$

$$ p = q_x \cdot 1 \cdot 1 \cdots 1 $$

$$ p = q_x $$

$$ p = p $$

This proves the base case of our induction.

Now, assume that uniqueness holds for all factorizations involving $ m-1 $ irreducible factors.

Consider an integer $ n $ with a minimal-length factorization of $ m $ irreducible elements, where each $ p_i > 1 $:

$$ n = p_1^{h_1} \cdot p_2^{h_2} \cdots p_m^{h_m} $$

Suppose $ n $ has an alternative factorization into $ m $ irreducible factors:

$$ n = q_1^{h_1} \cdot q_2^{h_2} \cdots q_t^{h_t} $$

This gives the equality:

$$ p_1^{h_1} \cdot p_2^{h_2} \cdots p_s^{h_s} = q_1^{h_1} \cdot q_2^{h_2} \cdots q_t^{h_t} $$

Let $ p_1 $ be a prime that divides at least one $ q_i $ on the right-hand side:

$$ p_1^{h_1} \cdot p_2^{h_2} \cdots p_s^{h_s} = q_1^{h_1} \cdots q_i \cdots q_t^{h_t} $$

We can cancel $ p_1 $ and $ q_i $ from both sides.

This reduces the number of irreducible factors in $ p $ to $ m-1 $.

By the induction hypothesis, this factorization must also be unique.

It follows that every $ q_i $ must be equal to some $ p_i $, except possibly for their order.

Thus, we have proven the uniqueness of the minimal-length factorization.

And so on.