# [FOM] New Proof of Fundamental Theorem of Arithmetic

Vaughan Pratt pratt at cs.stanford.edu
Fri Sep 25 02:48:03 EDT 2009

```joeshipman at aol.com wrote:
> Here's a simpler proof that avoids quoting Jordan-Holder:
>
> Let n=ab be divisible by a prime p. Consider the cyclic group Z_n of
> [snip]
> without having used GCDs or division with remainder.

Very elegant.  Perhaps that argument is in print somewhere, but if so it
evidently isn't getting the publicity it deserves.  Submitting a short
pdf to the College Mathematics Journal at cmj at oberlin.edu should have
only two possible outcomes, both good: they'll bounce it as known giving
a quick positive answer to whether it's known, or they'll publish it.

It occurs to me that your argument "at the bottom" of the division
lattice for n (the set of positive divisors of n ordered by
divisibility) works equally well in dual form "at the top" to prove the
following dual of Euclid's Lemma, from which FTA easily follows.

Lemma.  If p and q are distinct prime divisors of n then pq divides n.

We first prove:

Bezout's Identity, special case: if p and q are distinct prime divisors
of n then the subgroup G = {(ap + bq) mod n | a,b in Z} of Z_n is Z_n
itself.

Proof.  Since G contains subgroups of Z_n isomorphic to both Z_{n/p}
(set b = 0) and Z_{n/q} (set a = 0) and is contained in Z_n its order
must be divisible by both n/p and n/q, and must divide n.  But n is the
only such number, whence G = Z_n.  QED

(This argument avoids gcd's and division with remainder, your criteria.)

Proof (of Lemma).  Let p and q be distinct prime divisors of n.  By the
above case of Bezout's Identity there exist integers a,b such that (ap +
bp) ~ 1 mod n, that is, ap + bq = kn + 1 for some k.  Then dap + dbq =
dkn + d where d = n/q.  p divides three of these terms and hence divides
the fourth, namely d, whence d = pe.  Hence n = pqe whence pq divides n.
QED

Since these proofs are very natural it seems rather unlikely that
they've been overlooked, but it's definitely worth asking around.
(You'd think all the proofs of very old theorems had been found by now,
but I recently found a publishable proof of the interderivability of the
Pythagorean Theorem and Heron's area formula using Al-Karkhi's 11th
century quarter-squares rule, google for "Factoring Heron.")

Vaughan Pratt
```