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