# [FOM] New Proof of Fundamental Theorem of Arithmetic

George McNulty mcnulty at mailbox.sc.edu
Fri Sep 25 15:30:13 EDT 2009

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

Vaughan Pratt wrote:
> 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
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
```