[FOM] Only one proof

[Henry Cohn]

>But what about the Fundamental Theorem of Arithmetic?  All proofs I'm 
>aware of seem to boil down to one version or another of Euclid's GCD 
>algorithm.  Is there a different proof?

Here are a couple of different proofs.  The first is folklore, while the
second I learned from Shafarevich's book Discourses on Algebra.

Suppose there were positive integers with two different prime factorizations,
and let N be the smallest such integer.  Write N as a product of primes
in two ways as N = p_1 ... p_r = q_1 ... q_s.  No p_i can equal any q_j,
since otherwise they could be cancelled to lower N.  Without loss of
generality suppose p_1>q_1, and let M = (p_1-q_1) p_2 ... p_r.  This
number is less than N, so it has a unique prime factorization.  To obtain
one, we can replace p_1-q_1 with its factorization.  Because p_1-q_1 is
not divisible by q_1, this means M has a prime factorization that does
not include q_1.  However,
M = N - q_1 p_2 ... p_r = q_1 (q_2 ... q_s - p_2 ... p_r),
so M also has a prime factorization that does include q_1.  This
contradicts the minimality of N.

The second proof uses the more common route of proving that if a prime
divides a product, it divides one of the factors.  Suppose p is the smallest
prime for which this fails.  Then there are integers a and b such that
p divides ab but neither a nor b.  We can reduce a and b mod p to ensure
that 0 < a,b < p.  Write ab = pc.  Then 0 < c < p thanks to the bounds on
a and b.  All prime divisors of c are less than p, so they each divide one
of a and b.  We can cancel them and thus assume without loss of generality
that c = 1.  Then ab = p with 0 < a,b < p, which contradicts the primality
of p.  Thus, every prime that divides a product must divide one of the
factors, from which it's easy to prove the fundamental theorem of arithmetic.

Henry Cohn
cohn at microsoft.com

-----Original Message-----
From: fom-bounces at cs.nyu.edu [mailto:fom-bounces at cs.nyu.edu] On Behalf Of Vaughan Pratt
Sent: Saturday, September 05, 2009 4:06 AM
To: Foundations of Mathematics
Subject: Re: [FOM] Only one proof



joeshipman at aol.com wrote:
> That leaves Feit/Thompson as my best example of an important theorem 
> with essentially only one proof. Can anyone think of another? (It's not 
> enough that there is one idea common to all proofs unless that idea is 
> the only difficulty -- I'm looking for a theorem where all proofs are 
> essentially similar both globally and locally.) 

As we know from Gauss there are strikingly different proofs of the 
Fundamental Theorem of Algebra (that every univariate polynomial with 
complex coefficients has a complex root), although they all rely on 
topology.  (One would imagine there should also be a discrete 
nontopological proof using algebraic numbers, the obstacle there seems 
to be that the very existence of the algebraic numbers seems to depend 
on topology.)

But what about the Fundamental Theorem of Arithmetic?  All proofs I'm 
aware of seem to boil down to one version or another of Euclid's GCD 
algorithm.  Is there a different proof?

Vaughan Pratt
_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom