[FOM] Only one proof
Vaughan Pratt
pratt at cs.stanford.edu
Wed Sep 9 20:38:32 EDT 2009
Tim Chow (and others) wrote:
> There's a proof, sometimes called the "Hasse-Lindemann-Zermelo" proof,
> that proceeds directly by induction without reference to GCDs.
That's the only proof I know, viz:
Let the least counterexample be pr = qs with p<q prime and r,s nonempty
strings of primes. By leastness p does not appear in s, and cannot
divide q-p, whence p(r-s) = (q-p)s yields a smaller counterexample.
I find it hard to believe Fermat or Euler would have considered this a
"new proof," and I would be shocked if Gauss had. It's simply the
distillation to its essence of the only way it's ever been argued.
In any event, unlike the Fundamental Theorem of Algebra, which prior to
the end of the eighteenth century wasn't even known to be true, and for
which Gauss unsuccessfully sought a common distillation throughout much
of his life, the Fundamental Theorem of Arithmetic is not the sort of
deep number-theoretic fact that serious mathematicians prior to the 20th
century would have felt the need to revisit. It's just too elementary.
That degree of rigor in the well-understood arithmetic of factoring,
unlike the much less well-understood arithmetic of finding roots of
quintics etc., is largely confined to the 20th century.
> See http://math.uga.edu/~pete/factorization.pdf for more info.
This is Pete Clark's state-of-the-art analysis of the logic (or algebra
if you prefer) of factorization. In Clark's ordering of the logical
dependencies the concept of GCD is not even raised until Section 6. In
Section 4, Clark's Theorem 16 states that in the world of factorization
domains, being a unique factorization domain is the same thing as
satisfying (x | ab --> x|a or x|b) for all irreducibles x (an
EL-domain). Clark's proof begins with the sentence "The argument that
one uses in elementary number theory to deduce the fundamental theorem
of arithmetic from Euclid’s Lemma (and conversely) carries over without
essential change to this context," and the first word of that first
sentence is "the."
This makes clear that Clark does not view the proof of the Fundamental
Theorem of Arithmetic as depending logically on the GCD concept; for
him, as for me, it is the other way round: there are lots of GCD
algorithms (based on subtraction, division, shifting, etc.) but
essentially only one proof of the Fundamental Theorem of Arithmetic at
the core of all those algorithms. Furthermore I did not see anything in
Clark's paper saying or implying there might be another proof, though I
could well have overlooked it.
If I'm wrong on this (always a distinct possibility) then I'm sure there
are many on this list who would love to see this other argument
distilled down to its essence so as to allow it to be compared with the
argument above. However if it is thirty lines rather than three then it
might be tedious to show that it is essentially different, as opposed to
merely the wood rendered invisible by the trees.
Vaughan Pratt
More information about the FOM
mailing list