Here are a few more examples.

**Theorem.** There are infinitely many prime numbers.

**Proof.** Assume to the contrary that there are only finitely many prime numbers, and all of them are listed as follows: p_{1}, p_{2} ..., p_{n}. Consider the number q = p_{1}p_{2}... p_{n} + 1. The number q is either prime or composite. If we divided any of the listed primes p_{i} into q, there would result a remainder of 1 for each i = 1, 2, ..., n. Thus, q cannot be composite. We conclude that q is a prime number, not among the primes listed above, contradicting our assumption that ** all** primes are in the list p_{1}, p_{2} ..., p_{n}.

q

Proof by contradiction is often used when you wish to prove the impossibility of something. You assume it is possible, and then reach a contradiction. In the examples below we use this idea to prove the impossibility of certain kinds of solutions to some equations.

**Theorem.** There are no positive integer solutions to the diophantine equation x^{2} - y^{2} = 1.

**Proof.** (Proof by Contradiction.) Assume to the contrary that there is a solution (x, y) where x and y are positive integers. If this is the case, we can factor the left side: x^{2} - y^{2} = (x-y)(x+y) = 1. Since x and y are integers, it follows that either x-y = 1 and x+y = 1 or x-y = -1 and x+y = -1. In the first case we can add the two equations to get x = 1 and y = 0, contradicting our assumption that x and y are positive. The second case is similar, getting x = -1 and y = 0, again contradicting our assumption.

q

**Theorem.** There are no rational number solutions to the equation x^{3} + x + 1 = 0.

**Proof.** (Proof by Contradiction.) Assume to the contrary there is a rational number p/q, in reduced form, with p not equal to zero, that satisfies the equation. Then, we have p^{3}/q^{3} + p/q+ 1 = 0. After multiplying each side of the equation by q^{3}, we get the equation

There are three cases to consider. (1) If p and q are both odd, then the left hand side of the above equation is odd. But zero is not odd, which leaves us with a contradiction. (2) If p is even and q is odd, then the left hand side is odd, again a contradiction. (3) If p is odd and q is even, we get the same contradiction. The fourth case--p even and q even--is not posssible because we assumed that p/q is in reduced form. This completes the proof.

q

Proof by Contradiction is often the most natural way to prove the converse of an already proved theorem.

**The Converse of the Pythagporean Theorem.** If the (nonzero) three side lengths of a triangle--a, b and c--satisfy the relation a^{2} + b^{2} = c^{2}, then the triangle is a right triangle. (Assume the Pythagorean Theorem has already been proved.)

**Proof.** (Proof by Contradiction.) Suppose the triangle is not a right triangle. Label the vertices A, B and C as pictured. (There are two possibilites for the measure of angle C: less than 90 degrees (left picture) or greater than 90 degrees (right picture).)

Erect a perpendicular line segment CD as pictured below.

By the Pythagorean Theorem, BD^{2} = a^{2} + b^{2} = c^{2}, and so BD = c. Thus we have isosceles triangles ACD and ABD. It follows that we have congruent angles CDA = CAD and BDA = DAB. But this contradicts the apparent inequalities (see picture) BDA < CDA = CAD < DAB (left picture) or DAB < CAD = CDA < BDA (right picture).

q

- The cube root of 2 is irrational.
- There are no positive integer solutions to the diophantine equation x
^{2}- y^{2}= 10. - There is no rational number solution to the equation x
^{5}+ x^{4}+ x^{3}+x^{2}+ 1 = 0. - If a is a rational number and b is an irrational number, then a+b is an irrational number.

** Next==>**Proof by Contrapositive

**<==Back To **Direct Proofs