Proof by Contradiction

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.