# [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
dimensions.

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