Every composite number can be expressed as a product of primes proof
Answers
<b> First part of the proof </b>
We show that if not every number greater than 1 can be written as a product of primes, we end up in some kind of impossibility. So after that we conclude that it must be true that every number can be written as a product of primes.
So, now see what happens when somebody says that he/she knows a positive integer, greater than 1, which can not be written as a product of primes. In that case we ask him/her to mention all the numbers, greater than 1, that can not be written as a product of primes. One of these numbers must be the smallest: let's call it n. Of course, this number n cannot be 1. Further, it cannot be a prime number, because a prime number is a 'product' of a single prime: itself. So it must be a product of numbers. Thus-
n = ab
where both a and b are positive integers that are of course smaller than n. But: n was the smallest number that can not be written as a product of primes. So it must be possible to write a and b as products of primes, because they are both smaller than n. But then the product
n = ab
can be written as a product of primes as well. This is an impossibility because we said that n can not be written as a product of primes.
We have now shown the impossibility which exists if the first part of the theorem would not be true. In this way we have now proven the first part of the theorem.
<b> Second part of the proof </b>
Now we have to prove that there is only one way to write a positive number greater than 1 as a product of prime numbers.
To do this, we use the following lemma: if a prime number p divides a product ab, then it divides a or it divides b (Euclid's lemma). First we now prove this lemma. Well, assume now that p does not divide a. Then p and a are coprime and we have Bezout's identity that says that there must be integers x and y such that
px + ay = 1.
Multiplying everything with b gives
pbx + aby = b,
Remember that ab could be divided by p. So now, on the left-hand side we have two terms that are divisible by p. So the term on the right-hand side is also divisible by p. We have now proven that if p does not divide a, it must divide b. That proves the lemma.
Now we will prove that we can write an integer greater than 1 in only one way as a product of prime numbers. Take two products of primes A and B which have the same outcome. So we know for the outcome of the products that A = B. Take any prime p from the first product A. It divides the A, so it also divides B. Using several times the lemma that we just proved, we can see that p must then divide at least one factor b of B. But the factors are all primes themselves, so also b is prime. But we know that p is also prime, so p must be equal to b. So now we divide A by p and also divide B by p. And we get a result like A* = B*. Again we can take a prime p from the first product A* and find out that is equal to some number in the product B*. Continuing in this way, at the end we see that the prime factors of the two products must be exactly the same. This proves that we can write a positive integer as a product of primes in only one unique way.