The Unique Factorization Theorem

Euclid's Lemma (EL)

Lemma

For all integers and , and prime numbers , if , then or

Proof

Let and be arbitrary integers, and be an arbitrary prime number.
Using the elimination, we prove the impication:

Since is prime, the only positive divisors of are and , so the only possible values of are and .
However, , since , so we conclude that .

We conclude from Coprimeness and Divisibility that

Proposition - Generalization of Euclid's Lemma

Let be a prime number, and be a natural number, and be integers. If , then for some

I.e if in Euclid's Lemma was replaced with an an arbitrary number of factors, one of those factors would be divisible by

Unique Factorization Theorem (UFT)

Theorem - Fundamental Theorem of Arithmetic

Every natural number can be written as a product of prime factors uniquely, disregarding the order of those factors.

This is an extension of Prime Factorization, with uniquness.

Remark

We can further extend this as: for every natural number (), we can represent uniquely as the product

Where are positive integers, and are prime factors of .
For example, the prime divisors of 80 262 are 2, 3, 7, and 13, and we have

Even more generally, suppose , and the list of distinct primes , includes all prime numbers. Then

Where are non-negative integers.
Then we can write .

Proof

We have already proven in Prime Factorization that can be written as a product of prime factors. We now have to prove uniqueness.

We prove this result by strong induction on , where is the open sentence:
The natural number can be written as a product of prime factors uniquely, apart from the order of the factors

Base Case: The statement is true, since is a prime.

Inductive Step: Let be an arbitrary integers, where
Assume the inductive hypothesis, . We with to prove .
Now the integers is either prime or composite.

Case 1: If is prime, then is immediately true.

Case 2: If is composite, then we already know from Prime Factorization that it can be written as a product of primes.
Now suppose that can be written as a product of primes with factors, and as a product of primes with factors , so we have:

Since is composite, we must have

Now we have , from (1), we obtain (since .
Hence, by EL, for some .
If necessary, reorder the 's to that ???
Since and are both primes this means , and thus dividing (1) by , we obtain

Where .
Since , so , and
Since , so .
Thus, we have , so by the inductive hypothesis, is true.
But this means in (2), the two factorizations and of must be identical, apart from the order of the factors.
Then, since , this means that the two factorizations and of must be identical, hence proving in this case also.

The result is true for , and hence holds for all by POSI

Finding a Prime Factor (FPF)

Similar to the Sieve of Eratosthenes

Proposition

Every natural number is either a prime or has a prime factor less than or equal to

Proof

Suppose that is not prime.
Then by UFT, we can write , where , and are primes.
Let be the smallest prime factor of , so we have for .
Hence we obtain

And therefore, taking positive square roots, we have

Example

Determine whether is a prime number or not

From FPF, either is a prime, or it has a prime factor less than or equal to .
Now .
The only primes less than or equal to are , , , and .
Since none of these divide , we conclude that must be a prime number.