The Fundamental Theorem of Arithmetic

Theorem 2.20 (Fundamental theorem of Arithmetic). Let n be an integer greater than 1. Then it is possible to factorise (represent) n as a product of a finite number of irreducible elements (or prime number) p_j > 1:

where p_j, j = 1, ..., s, are all distinct, and the exponents h_j are positives and s ≥ 1. Moreover such factorisation is unique: if n can represented also as

with q_i distinct irreducible elements greater than 1, then the number of factors in the first factorisation is the same as in the second, and q_i and p_j are equal up to the order.

Proof. Existence of a factorisation. We use the induction principle 𝕀 on the integer n we want to factorise. If n = 2, we get 2 = 2, a factorisation composed by irreducible elements > 1. Suppose we have proven the existence of a factorisation for every positive integer k < n, k ≥ 2; we now have to prove it for n. If n is irreducible, nothing is left to prove, so let n be reducible, so it may be written as n = ab with a and b, both both ≥ 2 and smaller than n. Then by the inductive hyphotesis, a and b are factorisable as products of primes:

thus

It is a matter of grouping together, in the right-hand side, equal prime numbers in order to get the result in the form.

Uniqueness of the factorisation. In order to prove the uniqueness of the factorisation for any integer n, we proceed by induction, this time on the number m of irreducible factors in any factorisation of n. If m = 1, then the number n having that factorisation is an irreducible element (or prime number); p > 1: suppose that n = p has another factorization: q₁^k₁ q₂^k₂ ... q_t^k_t allora:

Being p a prime that divides the right side, p will divide also one of the factors of the right side; let p| q_i. Also q_i, is irreducible, thus it canno factorised, hence p = q_i. For the cancellation law valid in ℤ, we get:

This relation implies that all exponents on the right-hand side are null, otherwise we would have a product of integers greater than 1 whose results give 1. Then the right-hand side is q_i, hence p = q_i is the only factorization of n. We've thus prove the basis step of induction. We suppose the unicity of the factorization true for every factorization in m − 1 irriducible factors. Let n an integer with a factorization in m irriducible factors, and let

two factorisations of n in irreducible factors, the factorisation on the left side has m irreducibles factors, thus h₁ + h₂ + ... + h_s = m. Since, p₁ is a prime that divides the right side, it will divide also a q_i. As before, we have p₁ = q_i, thus they can both be canceled by both sides, and obtain

On the left side the number of irreducible factors is m − 1. By the inductive hypothesis the unicity of the factorization holds, thus the q_j coincide with the p_i, disregarding order. So the factorization of n is unique.□

Note as during the proo the equivalency in ℤ between prime element and irreducible element was frequently employed.

Il teorema precedente vale anche per interi arbitrari.

Proposition 2.24. Let z an integer ≠ 0 and ≠ ± 1, it can only be written in the form