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
_____________________________________________

Proofs that Every Natural Number Factors into Only One Unique Product of Primes

Date: 03/15/2012 at 00:16:30
From: Andy
Subject: Why does a number have exactly one set of prime factors

Why does a number have exactly one set of prime factors? 

If I look at 100, and find that it factors to 2 x 2 x 5 x 5, then why is
that the ONLY set of prime factors that can multiply out to get there? How
do I know that it can't be divisible by 3, say? or by 7?

By far the most confusing thing is that this principle is so ingrained
into our thinking that when I try to construct a proof, I find that I'm
using the thing I'm proving within the proof, itself!

For example, I can look at a rectangle of 3 x 7 silver balls and know that
if I try to divide it by 2, it won't work. Why? Because neither 3 nor 7 is
an even number. Ah, but the thinking behind that is: because 2 is not a
factor of 3 or 7, therefore the product of 3 x 7 cannot have 2 as a
factor.

You see? I end up USING that fact in trying to prove it.

I dream of attempting something very hard -- namely, explaining Public Key
Cryptography simply enough that interested adults and older children would
understand it. Key to this is how a number which is the product of two
large primes has no other factors. And even though it should be simple, I
can't explain it without begging the question.

A "layman's" answer, which showed it in graphical terms without being
necessarily watertight mathematically, would be great.



Date: 03/15/2012 at 06:10:56
From: Doctor Jacques
Subject: Re: Why does a number have exactly one set of prime factors

Hi Andy,

That is a very good question! 

The property you mention is known as the Fundamental Theorem of
Arithmetic: every natural number greater than 1 is the product of prime
numbers in an essentially unique way. This is often taken for granted, but
as you found out, this is not obvious at all. (In fact, a similar
statement can be false in other mathematical structures.)

This was proved by Euclid as proposition 14 of book IX, as described here:

   http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX14.html 

To a contemporary mind, however, Euclid's proof is rather hard to follow.
For starters, it requires proving all the propositions used in the proof
(most of them are in book VII). I will attempt to sketch a simpler proof.

The key lemma begins with a prime number p, and positive integers a and b.
I will use the symbol "|" to mean "divides."

   If p | ab, then p | a or p | b

(This is, in fact, Euclid's proposition VII.30.)

Once we have proved this, the result you seek follows easily: if the prime
p divides the product (q_1*...*q_n), where the q_i are prime (not
necessarily distinct), then p divides the product

   q_1*(q*2*...*q_n)

Our lemma tells us that either p | q_1, in which case p = q_1 because q_1
is prime; or p divides the other factor (q*2*...*q_n), and we can repeat
the argument until there is only one prime left, which will be p.

Let us go back to our lemma. Assume that there is a prime p and two
integers a and b such that p | ab, and p divides neither a nor b. Note
that we can assume that a and b are both greater than 1; indeed, if a = 1,
then p | b, and we are done.

Consider a fixed prime p, and the set of all the products ab that would be
counter-examples, i.e., the set of all numbers of the form ab which are
multiples of p and such that neither a nor b is a multiple of p. If there
is at least one counter-example, then there must be a smallest
counter-example, i.e., a product ab with the smallest possible value.
Assume now that ab is such a smallest counter-example (a and b need not be
unique, but the product ab is as small as possible).

I must emphasize that, if any counter-example exists, then a smallest
counter-example must exist: the choice of ab is legitimate, and this is
essential, since this will be used to produce a contradiction.

We note first that a and b must be smaller than p. Indeed, if a > p, then
this integer is also a multiple of p (since ab and bp are):

   (a - p)b = ab - bp

This is smaller than ab, and p divides neither b (by hypothesis) nor 
(a - p) (since otherwise p would divide a). This shows that (a - p)b is a
smaller counter-example, and contradicts our choice of ab as the smallest
counter-example.

So far, we have proved that 1 < a, b < p.

Since a < p, we can consider the greatest multiple of a, call it ka, that
is smaller than p. Let c = p - ka (c is actually the remainder of the
division of p by a). Now,

   * c > 0 (otherwise we would have ka = p, which is impossible since
     p is prime and 1 < a < p)

   * c < a (otherwise we could replace k by k + 1)

   * p does not divide c, because 0 < c < a < p

   * p divides cb = (p - ka)b = pb - k(ab), since p divides pb
    (obviously) and ab (by hypothesis)

Taken together, these properties show that cb is a smaller counter-example
than ab, and this contradicts our choice of ab. As this choice is always
possible if any counter-example exists, we conclude that such a
counter-example does not exist.

Please feel free to write back if you require further assistance.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/ 



Date: 03/15/2012 at 16:47:09
From: Andy
Subject: Thank you (Why does a number have exactly one set of prime factors)

Thank you very much for the complete answer!

I had a feeling that it was probably one of the fundamental principles of
mathematics, but there weren't enough "unique words" in the problem for me
to search for it on Google.

I was hoping to totally grasp it before thanking you, but to be honest,
although I see all the steps, I can't say that I've "got my brain round
it," as they say. But I'm confident that I will; and if I wait any longer,
you'll think I'm ungracious!

In fact, now I know what it is, thanks to you, I can probably search for
other explanations if I get stuck.

Thank you very much for your time!
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/