From: Martin GOLDSTERN <goldstrn@mail.zserv.tuwien.ac.at>
Newsgroups: sci.math.research
Subject: Re: The Book
Date: 17 Sep 1998 13:35:08 GMT

Tim Chow     tchow AT alum DOT mit DOT edu       wrote:
: Having said all this, I think the original question was a good one.  Does
: anyone have their own favorite examples of beautiful proofs that (1) are
: deeper than the standard elementary proofs that everyone knows yet (2) are
: accessible to a general audience of research mathematicians?

There is a recent book by Martin Aigner and Guenter Ziegler 
called "Proofs from The Book". (Springer, ISBN 3-540-63698-6)
The preface states "to a large extent this book reflects the views of
Paul Erdos". Also "everything in this book is supposed to be accessible
to readers [knowing only some] undergraduate mathematics". 
It contains 6 proofs of the infinitude of primes, starting with
Euclid's of course. One proof shows that the Fermat numbers F_n=2^2^n+1
must all be relatively prime [ use F_n*(F_n-2)=F_{n+1}-2 ]. 
Another uses Lagrange's theorem (element order divides group order) to
show that for any prime factor q of 2^p-1 we must have p|q-1, so p<q.
Another proof, due to Fuerstenberg, goes as follows:
 consider the "ideal topology" on Z, where a neighborhood base of m
 is given by the sets N_{m,b} = {m+kb: k in Z} for  b > 0.
 Since there are only finitely many remainders  mod b , one can see that
 these basic neighborhoods are not only open but also closed. 
 Now look at the union of all sets N_{0,p}, over all primes p.
 If there were only finitely many primes, this set would also be closed, 
 but its complement is just {1,-1} (since all other numbers have some prime
 divisor), and {1,-1} is certainly not open (all nonempty open sets are
 infinite)
Neat, isn't it? 
 
Martin.Goldstern@tuwien.ac.at
==============================================================================

From: propp@math.mit.edu (Jim Propp)
Newsgroups: sci.math.research
Subject: Re: The Book
Date: 16 Sep 1998 20:02:34 -0400

Here's that proof of the uniqueness of factorization in Z that I mentioned, 
courtesy of someone who prefers to be nameless:

Suppose N = p_1...p_r = q_1...q_s is the smallest positive integer with
two different factorizations.  Then no p_i equals any q_j.  WLOG, suppose
p_1 < q_1.  Let N' = (q_1-p_1)q_2...q_s.  Factor q_1-p_1 into primes to
turn this into a prime factorization of N' not including the factor p_1
(p_1 does not divide q_1-p_1 since p_1 does not divide q_1).  However,
writing N' = p_1(p_2...p_r-q_2...q_s) leads to a prime factorization
containing p_1.  This contradicts the minimality of N, since 0 < N' < N.

Jim Propp