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.

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.

**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.)

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.

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$.