Quite frequently you will find that it is difficult (or impossible) to prove something directly, but easier (at least possible) to prove it indirectly. The essence of the idea is simple: for example, suppose you want to know whether it is overcast or sunny, but you can't see the sky through your window. You usually can tell, indirectly, by the quality of light that you can see. Without formalizing the process, you make use of something like the following: If it is sunny I will be able to see areas of bright light and areas of shadow in the garden; I don't, so it must be (at least partially) overcast.
There are two methods of indirect proof: proof of the contrapositive and proof by contradiction. They are closely related, even interchangeable in some circumstances, though proof by contradiction is more powerful. What unites them is that they both start by assuming the denial of the conclusion.
Proof of the Contrapositive
The contrapositive of the statement $P\Rightarrow Q$ is $\lnot Q \Rightarrow \lnot P$. For example, the contrapositive of "If it is Sunday, I go to church'' is "If I am not going to church, it is not Sunday.'' Any sentence and its contrapositive are logically equivalent (theorem 1.1.3), but often it is easier and more natural to prove the contrapositive of a sentence.
Example 2.6.1 If $n>0$ and $4^n-1$ is prime, then $n$ is odd: Assume $n=2k$ is even. Then $$4^n-1=4^{2k}-1=(4^k-1)(4^k+1).$$ Therefore, $4^n-1$ factors (are both factors bigger than 1?) and hence is not prime. $\square$
Example 2.6.2 If $ab$ is even then either $a$ or $b$ is even: Assume both $a$ and $b$ are odd. Since the product of odd numbers is odd, $ab$ is odd. $\square$
Proof by Contradiction:
To prove a sentence $P$ by contradiction we assume $\lnot P$ and derive a statement that is known to be false. Since mathematics is consistent (at least we hope so), this means $P$ must be true.
In the case that the sentence we are trying to prove is of the form $P\Rightarrow Q$, we assume that $P$ is true and $Q$ is false (because $P\land\lnot Q$ is the negation of $P\Rightarrow Q$), and try to derive a statement known to be false. Note that this statement need not be $\lnot P$—this is the principal difference between proof by contradiction and proof of the contrapositive. In a proof of the contrapositive, we assume that $Q$ is false and try to prove that $P$ is false.
Example 2.6.3 $\sqrt 3\notin \Q$: Assume $\sqrt 3= a/b$ for positive integers $a$ and $b$ with no common factors (i.e., $a/b$ is in "lowest terms''). Then $a^2/b^2 = 3$, so $a^2=3b^2$. Now $3\vert 3b^2$ so $3\vert a^2$. This implies that $3\vert a$, so $a=3k$ for some $k$. Then $a^2=(3k)^2=9k^2=3b^2$, or $3k^2=b^2$. Now $3\vert b^2$, so $3\vert b$. Thus we've shown that 3 divides both $a$ and $b$, but this contradicts the fact that $a/b$ is in lowest terms. Hence, $\sqrt3$ cannot be written as a ratio of whole numbers. (We haven't proved that if $3\vert n^2$ then $3\vert n$, which we used twice. This can be proved in much the same way that we proved facts about even and odd numbers in section 2.1.) $\square$
Proof by contradiction makes some people uneasy—it seems a little like magic, perhaps because throughout the proof we appear to be `proving' false statements. A direct proof, or even a proof of the contrapositive, may seem more satisfying. Still, there seems to be no way to avoid proof by contradiction. (Attempts to do so have led to the strange world of "constructive mathematics''.) The following simple but wonderful proof is at least as old as Euclid's book The Elements.
Proof. Assume there are only finitely many primes $p_1,\ldots,p_k$. Let $n=p_1\cdots p_k+1$. Clearly $n\ge 2$, so by corollary 2.4.5, $n$ is divisible by some prime, say $p_i$. Obviously, $p_i\vert (p_1\cdots p_i\cdots p_k)$, so by theorem 2.2.1, $p_i\vert (n-p_1\cdots p_k)$; Since $n-p_1\cdots p_k=1$, $p_i\vert 1$, a contradiction.$\qed$
Note that this theorem does not give us a formula for constructing an infinite list of prime numbers. In particular, $n$ itself is not necessarily prime, though of course it might be. To date no one has devised a prime-generating formula, though many have tried. Are there any clues that might lead you to think that an indirect proof might be a good idea? The presence of not's in the statement of a theorem we are trying to prove is often (but not always!) an indication that an indirect argument is worth trying. Theorem 2.6.4 says that a certain set is not finite. Example 2.6.2 has the form $P\Rightarrow(Q\lor R)$. By denying the conclusion, we get two `solid facts' to work with: $\lnot Q$ and $\lnot R$. Working with composite numbers is often easier than working with primes, because the composite number can be factored; if by using indirect proof you can introduce a composite number it may help. Unfortunately, there are no hard and fast rules—deciding on what approach to use is a matter of experience and trial and error.
Euclid of Alexandria. Euclid, who flourished around 300 BC, is known to most high school students as the father of geometry. Surprisingly little is known of his life, not even his dates or birthplace. Shortly before 300 BC, Ptolemy I founded the great university at Alexandria, the first institution of its kind, and not unlike the universities of today. Euclid was recruited, probably from Athens, to head the mathematics department.
Euclid appears to have been primarily a teacher, not a great originator of new material. His Elements, unquestionably the most successful textbook of all time, often is thought to be an encyclopedia of all geometrical knowledge at the time. In fact, it is an elementary textbook covering geometry, arithmetic and algebra; Euclid himself knew and wrote about more advanced topics in mathematics. The perception that the Elements is only about geometry presumably is due to two facts: his name is most closely associated with geometry in modern elementary mathematics; and the mathematicians of antiquity, lacking modern algebraic notation, did all arithmetic and algebra in the language of geometry—for example, numbers were not thought of in the abstract, but as the lengths of line segments, or measures of areas or volumes.
The Elements consists of thirteen books containing much that is still familiar to students: most of elementary geometry, of course, including the Pythagorean Theorem; the theorem on the number of primes and the Fundamental Theorem of Arithmetic; and the Euclidean Algorithm, which we will see in section 3.3.
Two famous stories are told about Euclid. It is said that Ptolemy asked him if geometry could be learned without reading the Elements, to which Euclid replied, "There is no royal road to geometry.'' (This story is also told about Menaechmus and Alexander the Great, which perhaps diminishes its credibility somewhat.) In response to a student who questioned the use of geometry, Euclid reportedly ordered that the student be given three pence, "since he must needs make gain of what he learns.''
For more information, see A History of Mathematics, by Carl B. Boyer, New York: John Wiley and Sons, 1968; or An Introduction to the History of Mathematics, by Howard Eves, New York: Holt, Rinehart and Winston, 1976.
Exercises 2.6
Ex 2.6.1 If $n>0$ and $6^n-1$ is prime, prove that $n$ is odd.
Ex 2.6.2 If $a+b$ is odd, prove that $a$ or $b$ is odd.
Ex 2.6.3 Prove that $\sqrt 2$ is not a rational number. Hint: use the results of section 2.1.
Ex 2.6.4 Prove that $\sqrt 8$ is not a rational number.
Ex 2.6.5 If $a+b> 100$, prove that either $a> 50$ or $b> 50$.
Ex 2.6.6 Using $\R$ as the universe, prove that if $a$ is a rational number and $b$ is not a rational number, then $a+b$ is not a rational number.
Ex 2.6.7 An integer $n$ is said to be square-free if it has no divisors that are perfect squares (other than 1). Show that any divisor of a square-free integer is square-free.
Ex 2.6.8 Show that for every integer $n>2$ there is a prime between $n$ and $n!=1\cdot 2\cdots (n-1)\cdot n$. (Hint: look for prime factors of $n!-1$.)
Ex 2.6.9 Prove that if $3|n^2$ then $3|n$.