[FOM] New Proof of Fundamental Theorem of Arithmetic

[Vaughan Pratt]

joeshipman at aol.com wrote:
> Here's a simpler proof that avoids quoting Jordan-Holder:
> 
> Let n=ab be divisible by a prime p. Consider the cyclic group Z_n of 
> [snip]
> without having used GCDs or division with remainder.

Very elegant.  Perhaps that argument is in print somewhere, but if so it 
evidently isn't getting the publicity it deserves.  Submitting a short 
pdf to the College Mathematics Journal at cmj at oberlin.edu should have 
only two possible outcomes, both good: they'll bounce it as known giving 
a quick positive answer to whether it's known, or they'll publish it.

It occurs to me that your argument "at the bottom" of the division 
lattice for n (the set of positive divisors of n ordered by 
divisibility) works equally well in dual form "at the top" to prove the 
following dual of Euclid's Lemma, from which FTA easily follows.

Lemma.  If p and q are distinct prime divisors of n then pq divides n.

We first prove:

Bezout's Identity, special case: if p and q are distinct prime divisors 
of n then the subgroup G = {(ap + bq) mod n | a,b in Z} of Z_n is Z_n 
itself.

Proof.  Since G contains subgroups of Z_n isomorphic to both Z_{n/p} 
(set b = 0) and Z_{n/q} (set a = 0) and is contained in Z_n its order 
must be divisible by both n/p and n/q, and must divide n.  But n is the 
only such number, whence G = Z_n.  QED

(This argument avoids gcd's and division with remainder, your criteria.)

Proof (of Lemma).  Let p and q be distinct prime divisors of n.  By the 
above case of Bezout's Identity there exist integers a,b such that (ap + 
bp) ~ 1 mod n, that is, ap + bq = kn + 1 for some k.  Then dap + dbq = 
dkn + d where d = n/q.  p divides three of these terms and hence divides 
the fourth, namely d, whence d = pe.  Hence n = pqe whence pq divides n. 
  QED

Since these proofs are very natural it seems rather unlikely that 
they've been overlooked, but it's definitely worth asking around. 
(You'd think all the proofs of very old theorems had been found by now, 
but I recently found a publishable proof of the interderivability of the 
Pythagorean Theorem and Heron's area formula using Al-Karkhi's 11th 
century quarter-squares rule, google for "Factoring Heron.")

Vaughan Pratt