# [FOM] New Proof of Fundamental Theorem of Arithmetic

Vaughan Pratt pratt at cs.stanford.edu
Wed Sep 16 10:24:45 EDT 2009

```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
```