See here under "Euclid's Proof."
-Dan
Everyone knows that all numbers can be expressed as the product of prime numbers. But why is that? Is there a solid proof which shows that ALL numbers can be expressed as the product of primes numbers? Thanks.
Simplistically put, if you get the largest factor, and then the largest factor of the largest factor, so on so forth until you can't break it down any more, then all of your factors are primes. Each largest factor results in a prime when you divide the original number by it (by definition, if the other factor wasn't prime, then it isn't the LARGEST factor you've found). This holds for all numbers that can be divided (I.e. Not prime) and obviously, prime numbers are their own product. just in case my phrasing is confusing for the last part, where X is prime, X=X^1.
More formally we can use strong induction. A prime number is clearly a product of primes (1 prime), so let n be composite. Then n=ab where a,b<n. By strong induction a and b can be written as products of primes. Thus n can be written as a product o primes.