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 3-connected 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 n-th root of 2 is irrational.
Proof: The square root of 2 is irrational by a proof of Euclid. Now, let n > 2.
If 21/n is rational, say p/q, then 2 = pn/qn so that pn = qn + qn, which is impossible as conjectured by Pierre Fermat and proved by Andrew Wiles. Therefore, by the Principle of Mathematical Induction, 21/n is not rational for all integers n.
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.
The great 20th century mathematician, Paul Erdös (pronounced "airdish" in Hungarian), has said 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 great individual theorems that are easily grasped by this audience. At a future time, we may provide on these pages a more comprehensive list without regard to level of the result or the difficulty of the proof. Another issue is that we have not discussed the merit of one proof over another in terms of the extent of the areas in mathematics that the proof makes the result proved valid. For instance, under such a criterion, one might be justifiably tempted to regard a proof using Cross Ratio of, say, Ceva's Theorem or Menelaus' Theorem as superior to a proof using results that hold only in Euclidean Geometry.)
Our first proof, attributed to Euclid, appears as Proposition 20 in Book IX of the Elements. It is also referred to as Euclid's Second Theorem, the First Theorem being this: If a prime divides ab, then it divides either a or b.
The prime numbers or primes are numbers
2,3,5,7,11,13,17,19,23,...
that can not be resolved into smaller factors other than 1. In other words, a prime is divisible only by itself and 1. Primes are important mainly because of the Fundamental Theorem of Arithmetic that every number can be written UNIQUELY as a product of not necessarily distinct primes. Thus, 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.
1. The number of primes is not finite
PROOF.
Suppose that the number of primes is finite. Then the sequence of primes 2,3,5,... must end. Let the last prime in this sequence be p.
Let n = (2.3.. ... .p)+1.
n is divisible by some prime q. If q is among 2,3,5,...,p, then q would be a divisor of n and of the product 2.3.5....p and thus also of the difference n - 2.3.5...p = 1, which is impossible.
So p is not the largest prime. That is, the sequence of primes does not end. Q.E.D.
(Q.E.D., the abbreviation for Quod Erat Demonstrandum in Latin, means "that which was to be demonstrated." Sometimes this symbol is placed in this manner at the end of a proof to caution that the proof is over. It has also become the fashion instead to denote the end of a proof by placing a small rectangle with its shorter side horizontal. They call it a tombstone, meaning the death of suspicion of validity of the statement that was to be proved. )
Remarks on the proof:
a) Euclid's proof contains this statement: n is divisible by some prime q. This is true, for every integer bigger than 1 is either a prime or not. If it is prime, it is divisible by a prime which is itself. If it is not a prime, it is a product of primes and any one of those primes divides the product.
Euclid's proof also contains this statement: q would be a divisor of n and of the product 2.3.5....p and thus also of the difference n - 2.3.5...p = 1. Why is this true?
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) = ab-ac.
But b+(-c) = b-c. So a(b-c) = ab-ac.
Now, since q is a divisor of n and of the product,
n= qb for some b,
and 2.3...p = qc for some c. IS THIS CLEAR ABOUT THE b AND THE c?
Then n - 2.3....p = qb-qc = q(b-c), by the distributive law.
But n-2.3....p = 1 (see proof). So 1 = q(b-c), where q is an integer bigger than 1 and b-c is a non-zero integer (why?).
So 1 is a product of non-zero integers of which at least one integer is bigger than 1, wich is impossible, as we said in the proof.
b) 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" or an "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"
c) A merit of Euclid's proof
Euclid's proof can be accomplished also by taking any finite set of primes instead of the set of primes from 2 to p; in that case the proof would show the existence of a prime not in the chosen set. Can you do that proof?
Euclid's version has the merit of yielding the following interesting information:
After a prime p, there must be a prime at or before (2.3.5...p)+1. This is proved along the way in Euclid's proof.
The occurrence of primes
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 in 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. Notice also that Dirichlet's Theorem is a generalization of Euclid's result which you obtain by letting a = b = 1.
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 = 4k-1.
Theorem
There are infinitely many primes of the form 4m+3.
PROOF.
As in Euclid's proof, assume there
is only a finite number p1,p2,...,pn of primes of the form 4m-1.
Consider N = 4p1p2...pn - 1. Since N itself
is of the form 4m-1, 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 4m-1 which is of the form 4k+3.
Therefore, there
must be at least one prime factor p of the form 4m-1. p must be different (Why? Because each of the pi'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 p1,p2,...,pn.
Contradiction.
The Fundamental Theorem of Arithmetic mentioned earlier says that primes are the building blocks of natural numbers. The world of prime numbers is fascinating and strange!
For instance, although the number of primes is infinite, they do not make their appearance
in a uniform manner. Sometimes a prime appears soon after another prime,
like 17 and 19 or 71 and 73. There are 1,224 such pairs (p,p+2) below 100,000, and
8,169 below 1,000,000 [2].
In fact, the number of such prime pairs seems to be infinite.
Sometimes a prime does not appear for a long while. In fact, you can easily come up with such gaps of any length n where there are no primes. For instance, (1.2.3.4)+2, (1.2.3.4)+3, (1.2.3.4)+4 are three consecutive numbers of which none is a prime (why?). Can you use the idea here to come up with a million and one consecutive numbers of which none is prime? I think you can. You see, there are gaps of every length without primes in the sequence of "natural numbers" 1,2,3,… So Joseph Bertrand asked how long after you meet a prime the next higher prime must certainly make its appearance.
Bertrand verified[2] by computation that for n< 3000000 the following statement is true.
A proof that the postulate is in fact true and hence is a theorem was accomplished by others.
The occurrence of primes is one of the most interesting topics in the field of mathematics called "Number Theory." Although precise answers are not known to some questions like "how many primes are there less than a given number n?", there are now answers to questions like "approximately how many primes are there less than a given number n?"
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
