# Thread: Proof that all numbers are products of primes?

1. ## Proof that all numbers are products of primes?

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.

2. See here under "Euclid's Proof."

-Dan

3. Originally Posted by jsel21
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.
You could have done a web search .

4. Originally Posted by jsel21
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.
By "numbers" you mean positive integers. This result fails for the reals for example since there are no primes.

5. Originally Posted by jsel21
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.
It is called the Fundamental Theorem of Arithmetic. It can be found online or probably any Number Theory book you pick up.

6. 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.

7. 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.