[FOM] New Proof of Fundamental Theorem of Arithmetic

[Vaughan Pratt]

joeshipman at aol.com wrote:
> Since this proof does not use division with remainder or GCD, and since 
> the proof of the Jordan-Holder theorem is completely abstract and 
> involves only the group operation, and doesn't depend on any properties 
> of rings which have two operations, should this be counted as 
> essentially different from the usual proofs?

Ah, very nice.  I'm glad I included "I'm aware of" in my original 
statement "All proofs I'm aware of seem to boil down to one version or 
another of Euclid's GCD algorithm."

There's no need to appeal to the generality of Jordan-Holder, which (for 
finite groups) amounts to the observation that all paths in the modular 
lattice of normal subgroups of a finite group are isomorphic up to 
permutation.  For abelian groups this lattice is distributive, but 
restricting the argument to that case doesn't make the proof any less 
different.

The essential number-theoretic claim here is that the divisors of n form 
a finite distributive lattice which moreover is a product of chains. 
Your Jordan-Holder argument amounts to showing that for any two divisors 
a,b of n, the diamond with lcm(a,b) and gcd(a,b) at top and bottom and 
a,b at the sides commutes in the sense that lcm(a,b)/a = b/gcd(a,b) 
(from which it follows that lcm(a,b)gcd(a,b) = ab but this isn't needed).

The argument based on Jordan-Holder represents each divisor a of n as 
the order of the subgroup A = (n/a)Z_n of Z_n (so in particular n is 
represented as Z_n and 1 as the singleton nZ_n).  In this representation 
lcm(a,b) is represented as the group A+B = {a+b | a in A and b in B} 
(the addition being that of Z_n) while gcd(a,b) is represented as A&B = 
{a | a in A and a in B}, both being subgroups of Z_n.

The trick is to compose the epi m: Z_n --> Z_n/B defined as m(i) = i mod 
n/b with the inclusion i: A --> Z_n and observe that ker(mi) is A&B 
(intersection of A and B, the representation of gcd(a,b)) while im(mi) 
consists of the elements of (A+B)/B (as elements of Z_{n/b}).  But for 
any group homomorphism f: G --> H, im(f) ~ dom(f)/ker(f), here (A+B)/B ~ 
A/(A&B).  That is, lcm(a,b)/b = a/gcd(a,b).

Even without the applicability of Jordan-Holder to belian groups (as 
Peter Freyd likes to call nonabelian groups) this is still clearly a 
different proof from those that appeal to some version of Bezout's Identity.

The simple core of the latter class of proofs is that if pr = qs with 
primes p<q consists of two disjoint lists of primes then p does not 
appear in any factorization of the right hand side of p(r-s) = (q-p)s. 
The counterpart of that core for this Jordan-Holder proof seems to me to 
be the equally simple observation that lcm(p,q) = pq when p and q are 
prime, from which FT Arith follows straightforwardly.  This is 
essentially different from Euclid's Lemma, that if p divides ab then it 
divides one of a or b, usually proved from Bezout's Identity.

So I would say a proof of FT Arith via lcm(p,q) = pq, whether proved 
using the abstract-nonsense Jordan-Holder argument or by some more 
elementary number-theoretic argument, is different from the various 
proofs via Bezout's Identity in one or another disguise.

I looked in a few places but couldn't find this argument.  It must 
surely be somewhere---what does Conway think?  If not then you ought to 
put it in something like the College Mathematics Journal for the record.

Vaughan Pratt