Product of PrimesDate: 02/27/2002 at 01:14:03 From: Ganesh Subject: Prime Numbers Hello Dr. Math, Can you provide me with the proof that every non-zero positive integer can be written as a product of primes? Thank you, Ganesh Date: 02/27/2002 at 01:50:36 From: Doctor Schwa Subject: Re: Prime Numbers Hi Ganesh, Because of the definition of prime, every integer is either prime (and you're done), or is divisible by a smaller number. So, you can prove by induction: 2 is prime. Now suppose every number less than n can be written as a product of primes. Then either n is prime, or n = ab, where both a and b are smaller than n, and hence by the induction hypothesis both a and b can be written as a product of primes ... Next you'll probably be interested in the fundamental theorem of arithmetic, which says not only that every number can be written as a product of primes, but that there's only ONE WAY to do it. A very interesting page proving that uniqueness result (in very abbreviated fashion) is: How to discover a proof of the fundamental theorem of arithmetic. http://www.dpmms.cam.ac.uk/~wtg10/FTA.html It has a fascinating discussion about how the original authors might have thought of this proof, with some neat discussion of the ways of discovery. - Doctor Schwa, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/