Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Product of Primes


Date: 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/   
    
Associated Topics:
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/