Lesson Proof of Fundamental Theorem of Arithmetic

Proof of Fundamental Theorem of Arithmetic

This lesson is one step aside of the standard school Math curriculum.
It is intended for students who are interested in Math. So, it is up to you to read or to omit this lesson.
In any case, it contains nothing that can harm you, and every student can benefit by reading it.

This lesson is associated with the lesson Prime numbers and the Fundamental Theorem of Arithmetic of this module.
You can read this lesson after the previous one or independently of it.

A prime number (or prime for short) is a natural number that has exactly two divisors: itself and the number 1.
Because 1 has only one divisor, itself, we do not consider it as a prime number.
So, 2 is the first prime, 3 is the next prime, but 4 is not a prime because 4 has three divisors: 1, 2, and 4.
Numbers with more than two divisors are called composite numbers.

The first 20 primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, and 71.
The first 20 composite numbers are 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 22, 24, 25, 26, 27, 28, 30, 32, and 34.

The importance of prime numbers is that every natural number can be expressed as the product of primes.
For example,

,
,
,
,
,
,
,
,
,
,
,

and so on ...
So, the prime numbers are the building material to construct all natural numbers using multiplication.

The Fundamental Theorem of Arithmetic states that

Any natural number (except for 1) can be expressed as the product of primes.
For each natural number such an expression is unique.

So, the Fundamental Theorem of Arithmetic consists of two statements.
First one states the possibility of the factorization of any natural number as the product of primes.
The second one is about the uniqueness of such a factorization.

Proof.
First, we prove the existence of the prime factorization.
Let us start with the natural number 2.
It is already the prime number, so the required factorization is simply 2 = 2.

Now, let n be a natural number, and assume that all natural numbers less than n have a prime factorization.
If n is prime already, then the proof is completed.
If n is composite, then it has divisors other than 1 and itself. So, there are two natural numbers a and b such that ab = n and a, b < n.

By induction, a and b can be expressed as the products of primes:
and for primes , .

Then , and this is a required prime factorization for n.

Thus, according to the method of mathematical induction, we proved that any natural number (except for 1) can be expressed as the product of primes.

Next, we prove the uniqueness of the factorization of any natural number to the product of primes.

We will need two auxiliary supporting statements (theorems). In Mathematics such auxiliary supporting statements are usually called Lemmas.

Lemma 1
For two given natural (positive integer) numbers a and b consider the set of all integers {ax + by} that are linear combinations of a and b
with integer coefficients x and y. Let us denote this set of integers as S.
In this set S let us consider the sub-set of those integers that are positive (greater than zero). We denote this sub-set as P.
Take the minimum d = min {ax + by} over the sub-set P. Then d is the greatest common divisor of the numbers a and b.

Proof
First, we prove that divides .
Applying the general formula of dividing the integer number by the integer , we can write
, where .     (1)
We are going to show that the remainder is equal to zero.
Indeed, for some integers x and y.
Substitute this to the formula (1). You have
.
You can rewrite this as
, or .
The last expression for shows that belongs to the set S as the linear combination of a and b with integer coefficients.
If we assume that , then belongs to the sub-set P. By this reason, should be greater or equal to , because is the minimal number in the sub-set P.
This contradicts to the inequality of the formula (1).
Therefore, .
Thus, we proved that divides .
Similarly, divides .
Therefore, is the common divisor of integers and .
Since has a form , that is for some integers and , any common divisor of and divides .
Hence, the found number is the greatest common divisor of integers and .
The Lemma 1 is proved.

Lemma 2
If the prime number divides the product of two integers and , then divides at least one of or .

Proof
Suppose that doesn't divide , and prove that in this case divides .
Since doesn't divide and is the prime number, the greatest common divisor of and is equal to 1.
Then, according to the Lemma 1, there exist integers and such that .
Multiplication by yields the formula .
By assumption, divides ; therefore, divides . Clearly, divides . Hence divides .
The Lemma 2 is proved.

Now, the proof of the uniqueness of the factorization of any natural number to the product of primes is simple and straightforward.

Suppose that there are natural numbers with several prime factorizations.
Under this assumption, consider the smallest natural number that have several prime factorizations, let say
.

Then the prime divides , so by the Lemma 2 divides some .
Without loss of generality, we may assume divides .
Since and are primes, we must have = .

Then , and are two different prime factorizations of .
Since is less than , the smallest hypothetical natural number, which, by assumption, admits two different prime factorizations,
the factorizations above for are identical, which means that and for all i = 2, ..., r=s.
So, the original prime factorizations for are, actually, identical.

Thus, the proof of the uniqueness of the factorization of any natural number to the product of primes is completed.