[FOM] New Proof of Fundamental Theorem of Arithmetic

[George McNulty]

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