Results 1 to 7 of 7

Math Help - Proof that all numbers are products of primes?

  1. #1
    Newbie
    Joined
    Mar 2010
    Posts
    20

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,668
    Thanks
    298
    Awards
    1
    See here under "Euclid's Proof."

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,394
    Thanks
    1478
    Awards
    1
    Quote Originally Posted by jsel21 View Post
    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 .
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    Quote Originally Posted by jsel21 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by jsel21 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Feb 2011
    Posts
    7
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Counting products of a set of numbers
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: September 21st 2011, 03:56 PM
  2. Factoring numbers into product of primes
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 13th 2010, 05:17 AM
  3. Writing numbers as sum of primes
    Posted in the Number Theory Forum
    Replies: 16
    Last Post: December 21st 2009, 12:16 PM
  4. Products of numbers
    Posted in the Algebra Forum
    Replies: 3
    Last Post: December 5th 2009, 04:43 AM
  5. Euclid's theorem and primes numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 10th 2006, 07:33 AM

Search Tags


/mathhelpforum @mathhelpforum