[FOM] Only one proof

[Vaughan Pratt]

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