[FOM] New Proof of Fundamental Theorem of Arithmetic

Vaughan Pratt pratt at cs.stanford.edu
Wed Sep 16 04:09:57 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?

More to the point, if you "compile out" the non-abelian part, the core 
of this proof is the statement that lcm(p,q) = pq for primes p,q. 
(Obviously lcm(p,q) <= pq, the tricky part is equality.)  It hadn't 
occurred to me to proceed from that end instead of the usual gcd end, 
where gcd(p,q) = 1, but it works just as well.  So yes I'd call that a 
different proof, especially if you use the same group-theoretic argument 
as used in Jordan-Holder (which happens to work for non-abelian groups 
but that's a bit of a red herring here).

But even if you pass up the nice abstract-nonsense group-theoretic 
argument and use a more elementary number-theoretic argument for 
lcm(p,q) = pq, then unless there is some obvious reason why 
lcm(a,b)gcd(a,b) = ab, one that doesn't itself assume FTA (and for all I 
know there is one), it seems to me that any proof based on lcm(p,q) = pq 
should count as different from one based on gcd(p,q) = 1.

So I now know two proofs of FT Arith that I would consider essentially 
different.  Thanks, Joe!

The "I would consider" should not be neglected -- there may well be some 
way of identifying the two approaches, one that I don't currently see. 
However the option of the abstract-nonsense argument surely blocks that.

Vaughan Pratt

More information about the FOM mailing list