Skip to main content

Section 4.2 Proving that Something Does Not Exist

In mathematics, we sometimes need to prove that something does not exist or that something is not possible. Instead of trying to construct a direct proof, it is sometimes easier to use a proof by contradiction so that we can assume that the something exists.

We will illustrate this by proving the following proposition. Notice that the conclusion of the proposition involves trying to prove that an integer with a certain property does not exist. If we use a proof by contradiction, we can assume that such an integer \(z\) exists. This gives us more with which to work.

Proof.

We will use a proof by contradiction. So we assume that the proposition is false or that there exist integers \(x\) and \(y\) such that \(x\) and \(y\) are odd and there exists an integer \(z\) such that \(x^2 + y^2 = z^2\text{.}\) Since \(x\) and \(y\) are odd, there exist integers \(m\) and \(n\) such that \(x = 2m + 1\) and \(y = 2n + 1\text{.}\) So we get

\begin{align} x^2 + y^2 \amp = (2m + 1)^2 + (2n + 1)^2\notag\\ \amp = 4m^2 + 4m + 1 + 4n^2 + 4n + 1\notag\\ \amp = 2 ( 2m^2 + 2m + 2n^2 + 2n + 1 )\tag{2} \end{align}

Since the integers are closed under addition and multiplication, we see that \(2 ( 2m^2 + 2m + 2n^2 + 2n + 1 )\) is an integer, and so the last equation shows that \(x^2 + y^2\) is an even integer. Hence, \(z^2\) is even since \(z^2 = x^2 + y^2\) . So using the result in PropositionĀ 3.1, we can conclude that \(z\) is even and that there exists an integer \(k\) such that \(z = 2k\text{.}\) Now, using equation (2) above, we see that

\begin{align*} z^2 \amp = 2 (2m^2 + 2m + 2n^2 + 2n + 1)\\ 2k^2 \amp = 2 (2m^2 + 2m + 2n^2 + 2n + 1)\\ 4k^2 \amp = 2 (2m^2 + 2m + 2n^2 + 2n + 1) \end{align*}

Dividing both sides of the last equation by 2, we obtain

\begin{align*} 4k^2 \amp = 2 (2m^2 + 2m + 2n^2 + 2n + 1)\\ 2k^2 \amp = 2 (m^2 + m + n^2 + n) + 1 \end{align*}

However, the left side of the last equation is an even integer and the right side is an odd integer. This is a contradiction, and so the proposition cannot be false. Hence, we have proved that for all integers \(x\) and \(y\text{,}\) if \(x\) and \(y\) are odd integers, then there does not exist an integer \(z\) such that \(x^2 + y^2 = z^2\text{.}\)