Proof by Contradiction

Example 1: Proof of an infinite amount of prime numbers

Prove by contradiction that there are an infinite amount of primes.

Solution:

The first step is to assume the statement is false, that the number of primes is finite. Let's say that there are only n prime numbers, and label these from p₁ to p_n.

If there are infinite prime numbers, then any number should be divisible by at least one of these numbers.

Construct P, where we multiply all the prime numbers together and add 1, see above \(P = p_1p_2 ... p_n +1\). We then see that no prime will divide this number, as each of the primes divides P-1, and for a number to divide both P and P-1, the only possibility is one, which isn't prime. This means that P is a prime number, and as \(P > p_i \text{ for all } p_i\), this means there is a new prime, which means we now have a contradiction. This means that there must be an infinite number of prime numbers. QED

Example 2: Proof that 2 is irrational

Prove by contradiction that \(\sqrt{2}\) is irrational.

Solution:

Let us assume that \(\sqrt{2}\) is rational. This means that we can write \(\sqrt{2} = \frac{a}{b}\), with \(a, b \in \mathbb{Z}, b ≠ 0, gcd (a, b) = 1\). (Note - gcd stands for greatest common divisor). This means that \(\frac{a}{b}\) is a fraction in its lowest terms. Note here that this means that a and b cannot both be even, as then we would be able to cancel a factor of 2.

If \(\sqrt2 = \frac{a}{b}\), then \(2 = \frac{a^2}{b^2}\), which rearranges to \(a^2 = 2b^2\). This means that a² is even, which implies that a is also even.

(This above claim is easily verified. If a number is even, we can write it as 2k, with k as an integer. This squared equals 4k², which is also even. If a number is odd, then we can write it as \(2k + 1. (2k + 1)^2 = 4k^2 + 4k + 1 = 2 (2k^2 + 2k) +1\), which is odd. Thus, if a² is even, then so must be a.)

This means we can replace a with 2c, as a must be even. The value of c is unimportant, but it must be an integer.

Then, if \(a^2 = 2b^2\), we have \(4c^2 = 2b^2 \Rightarrow b^2 = 2c^2\). Following the same argument as above, this means b² is even, and in turn, b is even. Thus, we can write \(b = 2d, d \in \mathbb{z}\). This means that gcd (a, b) = gcd (2c, 2d) ≠ 1. (As the gcd will be a minimum of 2). This means there will not be a fraction in its lowest terms, and thus a contradiction.

We can now conclude that \(\sqrt2\) is irrational. QED

Example 3:

Prove there are no integers a and b such that

\(10a + 15b = 1\).

Solution:

Let us assume that we could find integers a and b that satisfy such an equation. We can then divide both sides by 5 to give \(2a + 3b = \frac{1}{5}\). If a and b are integers, and we multiply each by another integer (2 and 3 respectively, in this case), then sum them, there is no possible way that this could result in being a fraction, which is what the above condition requires. This leads us to a contradiction.

Thus, there are no integers a and b such that \(10a + 15b = 1\).

Example 4:

Use proof by contradiction to show that the sum of a rational number and an irrational number is irrational.

Solution:

Let us assume the sum of a rational number and an irrational number is rational. Let the rational number be denoted by a, and the irrational number denoted by b, and their sum is denoted by a + b. As a is rational, we can write it as \(a = \frac{c}{d}\), where d ≠ 0, and d and c integers, in the lowest possible terms. As a + b is rational, we can write \(a + b = \frac{e}{f}\), e, f ∈ ℤ, f ≠ 0, and the fraction in its lowest terms. Then we can write \(\frac{c}{d} + b = \frac{e}{f}\). This implies \(b= \frac{e}{f}-\frac{c}{d} = \frac{de-cf}{fd}\). As \(de-cf\) is an integer, and fd is also an integer, this implies that b would be able to be written as a rational number, which is a contradiction. Thus, the sum of a rational number and an irrational number is irrational.