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: p1, p2 ..., pn. Consider the number q = p1p2... pn + 1. The number q is either prime or composite. If we divided any of the listed primes pi 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 p1, p2 ..., pn.
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 x2 - y2 = 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: x2 - y2 = (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.
Theorem. There are no rational number solutions to the equation x3 + 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 p3/q3 + p/q+ 1 = 0. After multiplying each side of the equation by q3, 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.
Proof by Contradiction is often the most natural way to prove the converse of an already proved theorem.
The Converse of the Pythagorean Theorem. If the (nonzero) three side lengths of a triangle--a, b and c--satisfy the relation a2 + b2 = c2, 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, BD2 = a2 + b2 = c2, 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).
Next==>Proof by Contrapositive
<==Back To Direct Proofs
Back to Proofs