

Advanced summer program and resource for students age 1114
who show high promise and love mathematics


MATHEMATICS PROOF 

Great proofs
Mathematics, rightly viewed, possesses not only truth, but supreme beauty  a beauty cold and austere, like that of sculpture.
 Bertrand Russell (1872  1970)
Proof is the idol before whom the pure mathematician tortures himself.
 Sir Arthur Eddington (1882  1944), The Nature of the Physical World
Validity is the first test of proof. That is, a proof should be correct.
We shall define a great proof as a proof distinguished by beauty, surprise, and economy of a significant mathematical statement.
We shall define a significant mathematical statement as one that has wide applicability in the branch of mathematics in which the statement is made.
What is beauty in proof?
Since a quest for the answer would make us wander, we shall use the following as the definition of beauty in proof. A beautiful proof is one that evokes an aesthetical experience  consider all words in this sentence as undefined terms so that the discussion will rest!
Surprise in proof is like a trip where what you are seeking suddenly stands there. It is like going in a bus to see the Leaning Tower of Pisa; suddenly it comes in to view. Surprise in mathematics proof is the appearance of a result in an unexpected way from the addition of that last statement in the proof. It evokes a feeling of magic. But the greatest surprise is when a proof shows the relevance of one branch of mathematics to another. Examples are the uses of complex analysis for proofs in number theory or combinatorics.
Some times even physics gets in! An example [1] is the use of Kirchoff's Laws from electricity and 3connected planar graphs with n+1 edges to determine the perfect rectangles containing n squares. Of'course mathematics goes in surprising ways into physics. An example is the use of polynomial invariants of knots in quantum field theory.
We shall define economy in proof not only by the number of statements in the proof but also by how primitive the statements used are. Thus a proof using only beginning principles and definitions will be considered to possess economy as compared with a proof of the same result but achieved through using a result whose proof itself was longer.
Thus the following will not be accorded the status of a "short" proof:
The nth root of 2 is irrational for every integer n >1.
Proof: The square root of 2 is irrational by a proof of Euclid. Now, let n > 2.
If 2^{1/n} is rational, say p/q, then 2 = p^{n}/q^{n} so that p^{n} = q^{n} + q^{n}, which is impossible as conjectured by Pierre Fermat and proved by Andrew Wiles. Therefore, 2^{1/n} is not rational for every integer n >1.
Wiles' proof is not short. So the above proof using his proof does not possess economy.
Mathematicians refer to a beautiful proof possessing surprise and economy, an elegant proof. But beauty is the first test of elegance.
I have heard the great 20th century mathematician, Paul Erdös (pronounced "airdish" in Hungarian), say many a time that the greatest proofs must be contained in a book in the possession of God. After Erdös, mathematicians have come to call such a proof the "Book Proof." There is a book that is devoted to a sampling of such proofs.
(NOTE TO MATHEMATICIANS:
This essay being directed mainly to middle school and high school students who love math considers great proofs of a few significant statements that are easily grasped by this audience.)
By general consent the oldest Book Proof is attributed to Euclid; it appears as Proposition 20 in Book IX of the Elements. It is also referred to as Euclid's Second Theorem [2], the First Theorem being this: If a prime divides ab, then it divides either a or b.
A number p is said to be prime if (i) p >1 and (ii) p has no positive integer divisors except 1 and p.
Primes are important mainly because of the Fundamental Theorem of Arithmetic which states that every number can be UNIQUELY expressed as a product of primes in the sense that 24 = 2.2.2.3 and in any other expression of 24 as a product of primes there will be three 2's, one 3, and no other primes. (The Fundamental Theorem of Arithmetic is a corollary of Euclid's First Theorem.)
1. The number of primes is not finite
(English translation of Euclid's statement: Prime numbers are more than any assigned multitude of prime numbers.)
EUCLID'S PROOF.
For any finite set {p_{1},p_{2},...,p_{n}} of primes, consider m = p_{1}p_{2}...p_{n}+1. If m is prime it is not in the set since m > p_{i} for all i. If m is not prime it has a prime divisor p. If p is one of the p_{i} then p is a divisor of p_{1}p_{2}...p_{n} and hence is a divisor of (m  p_{1}p_{2}...p_{n} ) = 1, which is impossible; so p is not in the set. Hence a finite set {p_{1},p_{2},...,p_{n}} cannot be the collection of all primes.
Remarks on the proof:
a) Euclid's proof contains this statement: If m is not prime it has a prime divisor p. The proof is as follows  see Theorem 1 in [2]. Either m is prime, in which case there is nothing to prove, or it has divisors between 1 and m. If q is the smallest of these divisors, q is prime; for if q is not prime, there exists r, 1<r<q and r divides q so that r then divides m, which contradicts the definition of q.
b) Euclid's proof contains this statement: If m is not prime it has a prime divisor p. If p is one of the p_{i} then p is a divisor of p_{1}p_{2}...p_{n} and hence is a divisor of (m  p_{1}p_{2}...p_{n} ).
To justify this, we need the distributive law:
a(b+c) = ab+ac.
With c in place of c, a(b+(c))=ab+a(c) = abac.
But b+(c) = bc. So a(bc) = abac.
Now, since p is a divisor of m and of p_{1}p_{2}...p_{n}, m= pb for some b, and p_{1}p_{2}...p_{n} = pc for some c. IS THIS CLEAR ABOUT THE b AND THE c?
Then m  p_{1}p_{2}...p_{n} = pbpc = p(bc), by the distributive law.
But m  p_{1}p_{2}...p_{n} = 1 (see proof). So 1 = p(bc), where p is an integer bigger than 1 and bc is a nonzero integer (why?).
So 1 is a product of nonzero integers of which at least one integer is bigger than 1, which is impossible, as we said in the proof.
c) Proof by contradiction
Euclid's proof is given assuming that the
collection of all primes is finite and then deducing the absurd result that
there is a prime not in the finite collection.
The Latin phrase "reductio ad absurdum" means "reduction to the absurd."
It is one of the methods of proof. In English, it is called Proof by Contradiction," which is one type of "indirect
proof." The principle used is that Truth does not imply Falsity and
therefore that if an assumption leads to falsity it is not Truth. So, even the tool most often used in proof is based on a principle. Discussion
of this principle would take us into the philosophy of Logic of which
Aristotle is considered to have given the first interpretations.
G. H. Hardy [3] commented thus:
"The proof is by reductio ad absurdum, and reductio ad
absurdum, which Euclid loved so much, is one of a mathematician's finest
weapons. It is a far finer gambit than any chess gambit: a chess player may
offer the sacrifice of a pawn or even a piece, but a mathematician offers the
game"
d) An "existence" proof
Euclid's proof is perhaps the earliest example of an existence proof, which in this case is a nonexistence proof. That is, the proof only establishes that there cannot be finitely many primes. The proof does not exhibit the infinite set of the primes.
e) The occurrence of primes
Although Euclid's proof does not exhibit the infinite set of primes, it can be modified to present an infinite sequence of primes:
One argument:
Let x_{1} = 2, x_{2} = 3, and x_{k+1} = x_{1}x_{2}...x_{k} +1, for each k>1. Then if q_{k} is a prime dividing x_{k} then q_{k} divides x_{r}1 for r>k (why?) and hence q_{k} cannot divide x_{r} (why?). So no prime dividing x_{k} divides x_{k+1}. But since x_{k+1} >1, there is a prime dividing it, which is a prime not among the divisors of x_{1},x_{2},...,x_{k}.
Another argument ( See Section 2.2 in [2]):
Let 2,3,5,...,p be the set of primes up to p and let m = (2.3.5...p)+1. Then m is either prime, or divisible by a prime between p and m. This means if p is the nth prime p_{n} then p_{n+1} does not exceed m. That is, p_{n+1} ≤ p_{1}p_{2}...p_{n}+1, where p_{1} = 2, p_{2} = 3, etc. Then p_{n+1} ≤ p_{n}^{n} +1.
We can do better (see [2]): It is easily shown by applying the Principle of Mathematical Induction that
p_{n } < 2^{a}, where a = 2^{n}. This means p_{n } < p_{n+1 } < p_{n}^{2}. (Why?)
Joseph Bertrand postulated that in fact if n > 2, there is at least one prime p such that n < p < 2n2. A proof that the postulate is true and hence is a theorem was accomplished by others. An easier to remember version of Bertrand's postulate is that there is always a prime strictly between n and 2n, for n>2, but the actual postulate is the inequality in the preceeding sentence.
( Euclid's result says that there is an infinite number of primes among the natural numbers. It turns out that certain sequences contained in the natural numbers, while they omit an infinite number of natural numbers, still contain an infinite number of primes.
The most celebrated result on this matter was first conjectured by Euler and proved in 1837 A.D. by Dirichlet, a student of Gauss  yes! Carl Friedrich Gauss, referred to also as the prince among mathematicians.
Dirichlet's Theorem
If a is positive and a and b have no common divisor except 1, then there are infinitely many primes of the form an+b.
Thus, there are infinitely many primes of the form 4n+1, and similarly for
4n+3, 6n+1, and so on.
Clearly, not every integer of the form an+b, with a and b as above, is a prime (can you see it?). If they were, the proof of Dirichlet's Theorem would be immediate. Dirichlet is also famous for a method of proof called the Dirichlet Principle or, more popularly, the Pigeon Hole Principle.
While the proof of Dirichlet's Theorem is too difficult for inclusion here, there are simple proofs of its special cases.
We will present the case a = 4, b = 3.
Divided by 4, an integer can have only one of four remainders:0, 1, 2, 3. So an integer will have
one of the following forms: 4m, 4m+1, 4m+2, 4m+3. Numbers of the form 4m and 4m+2 are divisible by 2, and hence can not be prime (except for 2).
Now, numbers 4m+1 have the property that the product of any two of them is again
a number of the same form: (4m+1)(4k+1) = 4(k+m+4km)+1.
Also,numbers of the form 4m+3 may be written as 4m+3 = 4(m+1)1 = 4k1.
Theorem
There are infinitely many primes of the form 4m+3.
PROOF.
As in Euclid's proof, assume there
is only a finite number p_{1},p_{2},...,p_{n} of primes of the form 4m1.
Consider N = 4p_{1}p_{2}...p_{n}  1. Since N itself
is of the form 4m1, all of its prime factors can't be in the form 4m+1 (Why? Because if all prime factors are of the from 4m+1
then their product is of the form 4m+1, but N is of the form 4m1 which is of the form 4k+3.) Therefore, there
must be at least one prime factor p of the form 4m1. p must be different (Why? Because each of the p_{i}'s on dividing N gives a remainder of 1, whereas, p being a factor of N, leaves zero remainder on dividing N) from any of p_{1},p_{2},...,p_{n}.
Contradiction.)
f) A quality of a great proof
Unlike proofs introduced in courts of justice, the function of a mathematical proof is not to convince you that the statement is true, rather it is to show you why it is true. But a great proof also points to other directions  as a great theorem has many corollaries. Illustrative of this aspect is a famous proof by Leonard Euler of Euclid's result. Euler's proof remains one of the most influential proofs ever and reminds this writer of this quote of Christopher Marlowe: Was this the face that launched a thousand ships, and burnt the topless towers of Ileum?
REFERENCES
[1] The dissection of rectangles into squares , Brooks, R.L., Smith, C.A.B., Stone, A.H. and Tutte, W.T. (1940)
[2] An Introduction to the Theory of Numbers, G.H. Hardy and E.M. Wright, Oxford University Press, 1979
[3] A Mathematician's Apology, G. H. Hardy, Cambridge University Press, 1993
(G.R.T)
Ü BACK
MathPath  "BRIGHT AND EARLY"
Send suggestions to webmaster@mathpath.org
Copyright © 2001 MathPath
Last updated  June 21, 2006




 