We’ll start with a couple of good warm-up examples.
Example 11.2.1. No integer solutions.
There are no integers \(a,b\) so that \(2a+4b=1\text{.}\)
Scratchwork.
Now notice that this result hides some universal quantifiers:
\begin{equation*}
\forall a,b \in \mathbb{Z}, 2a+4b \neq 1
\end{equation*}
To prove this using a contradiction we need to assume the negation of this statement. That is, we will assume that
\begin{equation*}
\exists a,b \in \mathbb{Z} \st 2a+4b=1.
\end{equation*}
So let \(a,b\) be integers so that \(2a+4b=1\text{.}\) But from this we have (after a quick division by 2)
\begin{equation*}
a + 2b = \frac{1}{2}
\end{equation*}
and this is sufficient to get a contradiction;
\(a \in \mathbb{Z}\) and
\(2b \in \mathbb{Z}\) so their sum must be an integer. We just need to write this up nicely
155 .
Proof.
Assume, to the contrary, that there exist integers \(a,b\) so that \(2a+4b=1\text{.}\) This implies that
\begin{equation*}
a + 2b = \frac{1}{2}
\end{equation*}
which gives a contradiction because the sum of integers is also an integer. Consequently, there can be no such integer \(a,b\) and the result follows.
Example 11.2.2. Another no integer solutions.
There are no integers \(a,b\) so that \(a^2-4b=3\text{.}\)
Solution.
Proof.
Assume, to the contrary that \(a,b\) are integers so that \(a^2-4b=3\text{.}\) Hence \(a^2=4b+3\text{.}\) Consequently \(a\) must be odd (otherwise the LHS is even while the RHS is odd). So we can write \(a=2k+1\) for some integer \(k\text{.}\) Hence
\begin{equation*}
(2k+1)^2 = 4b+3
\end{equation*}
and so
\begin{equation*}
4k^2+4k+1 = 4b+3
\end{equation*}
which means that
\begin{equation*}
4(k^2+k-b) = 2.
\end{equation*}
And since \(k^2+k-b \in \mathbb{Z}\text{,}\) this implies that \(2\) is divisible by 4. This is clearly false and so we have arrived at a contradiction. Thus there can be no such integers \(a,b\) and the result holds.
Time for something a bit more substantial — a result about irrational numbers. Recall the definition of rational and irrational numbers.
Definition 11.2.3.
Let \(q\) be a real number. We say that \(q\) is rational if it can be written \(q = \frac{a}{b}\) where \(a,b \in \mathbb{Z}\) with \(b \neq 0\text{.}\) If \(q\) is not rational we call it irrational. We will denote the set of irrational numbers as \(\mathbb{I}\text{,}\) and note that \(\mathbb{I} = \mathbb{R} - \mathbb{Q}\text{.}\)
We note that the notation,
\(\mathbb{I}\text{,}\) is not standard, and some authors will use
\(\mathbb{P}\) or
\(\mathbb{K}\text{.}\) Unfortunately there is no widely accepted standard notation for the set of irrational numbers. When you do make use of a particular notation for irrational numbers
156 , and you are unsure if your reader knows that notation, we recommend that you devote a quick short sentence clarifying to explain.
Thus a number \(q\) is irrational when (writing it with quantifiers)
\begin{gather*}
\forall a,b\in \mathbb{Z}, \left( \frac{a}{b} \neq q \right).
\end{gather*}
So a good way to reach a contradiction when working with irrational numbers, is to show that a number that you have assumed to be irrational can actually be written as a ratio of integers. We use exactly this approach for the next result.
Result 11.2.4.
The sum of a rational number and an irrational number is irrational.
We start by assuming that the result is actually false and then work our way to a contradiction — namely that the number we assumed to be irrational is actually rational. It pays, especially when starting out with proof by contradiction, to write statements carefully with with quantifiers, so that we can also write down the negation carefully. The original statement is
\begin{equation*}
\forall x \in \mathbb{Q}, \forall y \in \mathbb{I}, x+y \in \mathbb{I}
\end{equation*}
and its negation is
\begin{equation*}
\exists x \in \mathbb{Q} \st \exists y \in \mathbb{I} \st x+y \not\in \mathbb{I}
\end{equation*}
We can simplify this a bit because we know that \(x+y \in \mathbb{R}\text{,}\) so if it is not irrational, it must be rational:
\begin{equation*}
\exists x \in \mathbb{Q} \st \exists y \in \mathbb{I} \st x+y \in \mathbb{Q}.
\end{equation*}
Now we assume this statement is true. And hence we can find a rational number, \(x = \frac{a}{b}\text{,}\) and an irrational number, \(y\text{,}\) and their sum \(x+y\) is rational. One way we could get the contradiction, is to leverage the facts we have (by assumption)
\begin{equation*}
x \in \mathbb{Q} \qquad y \in \mathbb{I} \qquad \text{and} \qquad x+y \in \mathbb{Q}
\end{equation*}
to reach a contradiction; in this example we’ll show that \(y \in \mathbb{Q}\text{.}\)
Since \(x\in \mathbb{Q}\) we know that there are integers \(a,b\) so that
\begin{equation*}
x = \frac{a}{b}.
\end{equation*}
similarly since \(x+y\in \mathbb{Q}\) we know that there are integers \(c,d\) so that
\begin{equation*}
x + y = \frac{c}{d}.
\end{equation*}
But now we can use these to obtain more information about \(y\text{:}\)
\begin{align*}
y \amp = (x+y) - x\\
\amp = \frac{c}{d}- \frac{a}{b} = \frac{cb-ad}{bd}
\end{align*}
But since all of \(a,b,c,d \in \mathbb{Z}\text{,}\) we’ve just shown that \(y\) is rational — contradiction!
Time to write it up. When we do so we should definitely be careful and show that those denominators are not zero.
Proof of Result 11.2.4.
We prove the result by contradiction. Assume that the result is false, and so there is a rational number \(x\) and an irrational number \(y\) whose sum \(z=x+y\) is rational. Since \(x\) and \(z\) are rational, \(x = a/b\) and \(z=c/d\) for some \(a,b,c,d \in \mathbb{Z}\) with \(b,d \neq 0\text{.}\) But now
\begin{align*}
y &= z-x = \frac{cb-ad}{bd}
\end{align*}
with \(bd \neq 0\) and so \(y\) must be rational. This contradicts our assumption that \(y\) was irrational. Hence the result is true.
When we use proof by contradiction to prove an implication, we just have to negate carefully. Say our statement \(P\) is of the form
\begin{gather*}
P \equiv \Big( \forall x \in S, Q(x) \implies R(x) \Big)
\end{gather*}
Our proof by contradiction needs us to prove that the negation of this statement implies a contradiction. So negating carefully:
\begin{align*}
(\neg P) \amp \equiv \neg\Big(\forall x \in S, Q(x) \implies R(x) \Big) \\
\amp \equiv \exists x\in S \st \neg\Big( Q(x) \implies R(x)\Big)\\
\amp \equiv \exists x\in S \st \Big(Q(x) \land \neg{R(x)} \Big)
\end{align*}
So our proof will start by assuming the existence of some \(x \in S\) such that \(Q(x)\) is true and \(R(x)\) is false. Of course, we should make sure that we alert the reader that we are using proof by contradiction. We might say “Suppose the statement is false” or something similar. Here is example of this in action:
Result 11.2.5.
Let \(a,b \in \mathbb{Z}\) with \(a \geq 2\text{.}\) Then \(a\) does not divide \(b\) or \(a\) does not divide \(b+1\text{.}\)
This statement has an implication hiding inside and can be written as
\begin{equation*}
\forall a,b \in \mathbb{Z}, \Big[ (a \geq 2) \implies \big( (a \nmid b) \lor (a \nmid(b+1) ) \big) \Big]
\end{equation*}
so when we negate it we obtain
\begin{equation*}
\exists a,b \in \mathbb{Z} \st \Big[ (a \geq 2) \land \big( (a \mid b) \land (a \mid (b+1)) \big) \Big]
\end{equation*}
We’ll start
157 our proof by assuming that we can find such integers
\(a,b\text{,}\) so that
\(a \geq 2\) and
\(a \mid b\) and
\(a \mid (b+1)\text{.}\) From this we’ll reach a contradiction.
Proof.
Assume, to the contrary, that there is some \(a,b \in \mathbb{Z}\) so that \(a \geq 2\) and \(a\) divides both \(b\) and \(b+1\text{.}\) This then implies that there exists \(k,\ell \in \mathbb{Z}\) such that \(b=ak\) and \((b+1) = a\ell\text{.}\)
But then \(1 = (b+1)-b = (\ell-k) a\text{.}\) Since \(\ell -k \in \mathbb{Z}\) this implies that \(a\) divides \(1\text{.}\) This means that \(a=1\) or \(a=-1\text{.}\) This contradicts our assumption that \(a \geq 2\text{.}\) Hence the result is true.
This is not the only way to prove the above result and we could give a quick contrapositive proof which as some similarities with our proof above.
Proof.
We prove the contrapositive. So let \(a,b \in \mathbb{Z}\) and assume that \(a \mid b\) and \(a \mid (b+1)\text{.}\) Then we know that \(b = ak, (b+1)=a\ell\) for some \(k,\ell \in \mathbb{Z}\text{.}\) But then this tells us that
\begin{equation*}
1 = (b+1)-b = a (k-\ell)
\end{equation*}
and so \(a \mid 1\text{.}\) However the only divisors of \(1\) are \(1,-1\text{.}\) And thus we know that \(a \lt 2\) as required.
Subsection 11.2.1 The irrationality of \(\sqrt{2}\)
The existence of a real quantity whose square is \(2\) follows directly from applying Pythagoras’s Theorem to the following simple triangle.
It is, however, much less obvious that \(\sqrt{2}\) cannot be expressed as the ratio of two integers; that result is one of the most famous in mathematics. Its proof, and so the proof of the existence of irrational numbers, is generally attributed to a member of the Pythagorean school in the 5th century BC, typically Hippasus of Metapontum. The evidence that exists linking Hippasus to the discovery of irrational numbers suggests that he was not praised for his work, but, rather, that he was expelled from his school. Some accounts indicate that he was even drowned as punishment! At the time the Pythagorean school thought that the positive integers numbers were somehow fundamental and beautiful and natural. The natural numbers were almost mystical objects and could be deployed to explain the universe. That such a simple and beautiful geometric object — the hypotenuse of a right-angle triangle — could not be expressed as the ratio of natural numbers was truly shocking. In some sense, it broke the link between number and the world.
Theorem 11.2.6.
The number \(\sqrt{2}\) is not rational.
We prove this result by finding a contradiction — that \(\sqrt{2}\) is both rational and irrational. The same proof can be made to work (with minor adjustments) for any prime number. A key part of the proof is understanding that when we write a rational number
\begin{equation*}
q = \frac{a}{b}
\end{equation*}
that we can insist that \(a,b\) do not have common factors. If we do have a representation \(q = \frac{c}{d}\) where \(\gcd(c,d) \gt 1\text{,}\) then we can divide both numerator and denominator by that common factor and set
\begin{equation*}
q = \dfrac{c}{d} = \frac{c/\gcd(c,d)}{d/gcd(c,d)} = \frac{a}{b}
\end{equation*}
where the new numerator and denominator,
\(a,b\) have no common factors. In this way, the resulting
\(a,b\) are the
smallest integers whose ratio represents that rational number. Using this idea, our proof works by assuming that
\(\sqrt{2}\) is rational and so can be represented by a smallest
\(a,b\) (ie with no common factors). We then obtain a contradiction by showing that the numerator and denominator do have a common factor. Along the way we will make use of a result we proved earlier
158 .
Let \(n \in \mathbb{Z}\text{.}\) Then \(n^2\) is even if and only if \(n\) is even.
Proof.
We prove the result by contradiction, and so assume that \(\sqrt{2}\) is rational. Thus we can write \(\sqrt{2} = \frac{a}{b}\) where \(a,b \in \mathbb{Z}\) and \(a\) and \(b\) have no common factors. Hence \(2 = \frac{a^2}{b^2}\text{,}\) which can be rewritten as \(2b^2 = a^2\text{.}\)
This implies that \(a^2\) is even and so (by the above fact) \(a\) must be even. Thus we can write \(a = 2 c\) for some \(c \in \mathbb{Z}\text{.}\)
Substituting \(a=2c\) into \(2b^2=a^2\) we find \(2 b^2 = 4 c^2\text{,}\) which implies \(b^2 = 2 c^2\text{.}\)Hence \(b^2\) is even and so \(b\) must be even.
Since both \(a\) and \(b\) are even, they must have a common factor of \(2\text{.}\) This contradicts our assumption that \(a\) and \(b\) have no common factors. Hence the result is true and \(\sqrt{2} \not\in\mathbb{Q}\text{.}\)
Here is another result with a similar proof.
Result 11.2.7.
Let \(a,b,c\) be odd integers. Then the polynomial \(ax^2 + bx + c\) has no rational zeros.
Proof.
Assume, to the contrary, that there are odd \(a,b,c\) and rational \(x\) so that \(ax^2+bx+c=0\text{.}\) Since \(x\) is rational, we know that \(x=\frac{k}{n}\) for some integers \(k,n\) with \(n \neq 0\text{.}\) Further, we can assume that \(k,n\) have no common factors; if they do have common factors, remove them. Then
\begin{equation*}
a\left(\frac{k}{n}\right)^2+b\left(\frac{k}{n}\right)+c = 0
\end{equation*}
and so (multiplying through by \(n^2\))
\begin{equation*}
ak^2+bkn+cn^2 =0
\end{equation*}
Now consider the parity of \(k\) and \(n\text{.}\) There are four possibilities
If \(k,n\) are both odd, then since \(a,b,c\) are odd, the LHS is also odd, and so cannot equal zero.
If \(k\) is even and \(n\) is odd, then \(ak^2\) and \(bkn\) are even, and \(cn^2\) is odd. Hence the LHS is odd and so cannot equal zero.
Similarly, if \(n\) is even and \(k\) is odd, then \(bkn\) and \(cn^2\) are even and \(ak^2\) is odd. Again this implies the LHS is odd and so cannot equal zero.
Finally, if \(k,n\) are both even, then this contradicts our assumption that \(k,n\) have no common factors.
Thus there cannot exist such \(k,n\) and hence there is no such rational \(x\text{.}\)
Subsection 11.2.2 The infinitude of primes
Here is wonderful result about a fundamental property of numbers — that there are an infinite number of primes. The first recorded proof of this is due to Euclid in his Elements
161 from around 300 BC. The result does not rely on unique prime factorisations, but it does require the fact that every integer greater than 1 has a prime divisor. We prove this first via strong induction — in fact we did this back in
Example 7.2.20.
Result 11.2.9.
Let \(n \in \mathbb{N}\) so that \(n \geq 2\text{.}\) Then \(n\) is divisible by a prime number.
Proof.
Armed with this result, we can prove that the set of primes is not finite.
Theorem 11.2.10. Euclid — 300 BC.
There are infinitely many primes.
We will prove this using a “proof by contradiction”. We assume that there are only a finite number of primes and then deduce a contradiction. If there are a finite number of primes, we can list them out \(\set{p_1,p_2, \dots p_r}\) and we can form the new number \(N = p_1 p_2 \dots p_r\) — Now \(N+1\) is not on our list and it is not divisible by any of the primes. This will be the source of the contradiction (with a little more work).
Proof.
Assume there are a finite number of primes. Since the primes are finite, we can write a finite list containing all of them — \(p_1, p_2, \dots, p_n\text{.}\) Now let \(N = (p_1 p_2 \dots p_r)\) be a product of all the primes. Since the list of primes is finite, we know that \(N\) is finite. Now either \(N+1\) is prime or not.
If \(N+1\) is prime then since \(N+1\) is bigger than all the primes on the list, \(N+1\) is not in our list of prime numbers. This gives a contradiction since our list was assumed to be all the primes.
-
If \(N+1\) is not prime then, by the above result, it must be divisible by one of the primes in our list — say \(p_k \mid (N+1)\text{.}\) Hence we can write \(N+1 = p_k a\) for some \(a \in \mathbb{N}\text{.}\) Similarly we can write \(N = p_k b\) for some \(b \in \mathbb{N}\text{.}\) But then
\begin{equation*}
1 = (N+1) - N = p_k (a-b).
\end{equation*}
This implies that \(1\) is divisible by \(p_k\) which is clearly false.
Thus \(N+1\) is not divisible by any prime on our list and so there must be some prime that is not contained in our list. Again this gives a contradiction since our list as assumed to contain all primes.
In both cases a contradiction is obtained and hence the result is true.
