[FOM] New Proof of Fundamental Theorem of Arithmetic

Vaughan Pratt pratt at cs.stanford.edu
Sat Sep 26 07:26:40 EDT 2009

George McNulty wrote:
> Vaughan,
>       See page 282 of Joseph Rotman's  Advanced Modern
> Algebra (a thousand page graduate algebra mass) for a
> version of the proof using the Jordan-H\"older Theorem
> to get the uniqueness of the prime factorization of integers.
> G

Thanks for that pointer, George, which confirms my guess that some 
expositor of JH must surely have made that point already.  This is why I 
didn't express any great enthusiasm for the likely originality of Joe's 
original argument applying JH directly, and why I pointed out in my 
response to Joe's earlier posting (the one claiming novelty for this 
application of JH) that lcd(a,b)/a = b/gcd(a,b) could be proved 
mentioning only finite cyclic groups, which slightly simplifies the more 
general JH argument.  I also mentioned somewhat cryptically perhaps that 
the further specialization to the top of the division lattice for Z_n 
further simplified the proof of FTA by this method.  Independently (I 
suspect) Joe gave the dual argument at the bottom of that lattice, 
prompting my response to Joe spelling out my earlier cryptic remark in 
detail equivalent to Joe's.

For the sake of having a definite null hypothesis (the core of the 
scientific method even in mathematics), Joe and I hypothesize (if he 
doesn't mind my rephrasing his claim in this way) that this dual pair 
(top and bottom) of extremal applications of the lcd(a,b)/a = b/gcd(a,b) 
principle in the particularly simple setting of cyclic groups (Z and 
Z_n) constitutes a pair of new proofs of the FTA, or a single proof if 
one accepts that the evident order self-duality in the lattice of 
subalgebras of a cyclic group identifies proofs exploiting it.  At the 
top one proves that if distinct primes p and q divide n then so does pq 
(does this principle have a name?), while at the bottom one proves 
Euclid's Lemma that if prime p divides ab it divides one of a or b.

The cyclic-group-based argument I gave for lcd(a,b)/a = b/gcd(a,b) is 
the generic way of factoring the division lattice for n starting 
anywhere, not necessarily with prime a,b but merely any a,b incomparable 
in the division lattice (to make the induction well-founded).  This is a 
kind of root proof from which the two extremal proofs can be extracted. 
  This organization suggests that mere equivalence of proofs might be 
too simple minded, and that they should be compared along one or more 

The patent office's stated criterion for novelty is obviousness to 
someone skilled in the art, but the one they use in practice is the 
ostensibly weaker condition of evidence of prior art.  Who knows how 
patent clerks think, especially when they come up with E = mc^2, but I 
imagine their reasoning might be that if it was so darned obvious then 
why didn't someone do it already?

In this case, if no one has previously stripped JH down to its 
cyclic-group essence when applying it to FTA, why not?  Good taste in 
minimality of proof should not settle for less.

Vaughan Pratt

More information about the FOM mailing list