- Assume the statement is false. Write down its negation clearly: "Assume, for contradiction, that…"
- Deduce consequences from that assumption using correct algebra and known facts.
- Contradict: reach something impossible — a number that is both even and odd, an integer equal to a fraction, a fraction not in lowest terms when you said it was.
- Conclude: "This is a contradiction, so the assumption was false and the statement is true."
The first line is worth a mark on its own, and getting it wrong wrecks the proof. The negation must be true in exactly the cases where the statement is false.
| Statement | Assume, for contradiction… |
|---|---|
| $\sqrt{2}$ is irrational | $\sqrt{2}$ is rational, so $\sqrt{2} = \dfrac{a}{b}$ with $a, b$ integers with no common factor |
| There are infinitely many primes | There are finitely many primes, $p_1, p_2, \ldots, p_n$ |
| There is no greatest even number | There is a greatest even number, $N$ |
| If $n^2$ is even then $n$ is even | $n^2$ is even and $n$ is odd |
| There are no integers $a, b$ with $a^2 - 4b = 2$ | There are integers $a, b$ with $a^2 - 4b = 2$ |
| For all $x > 0$, $x + \dfrac{1}{x} \geqslant 2$ | There is some $x > 0$ with $x + \dfrac{1}{x} < 2$ |
Prove that for any integer $n$, if $n^2$ is even then $n$ is even.
Prove that there is no greatest even number.
Prove that there are no integers $a$ and $b$ for which $a^2 - 4b = 2$.
Prove that there are no positive integers $x$ and $y$ with $x^2 - y^2 = 10$.
Prove that $\sqrt{2}$ is irrational.
Prove that $\log_2 3$ is irrational.
Given that $\sqrt{2}$ is irrational, prove that $3 + 5\sqrt{2}$ is irrational.
Prove that there are infinitely many prime numbers.
Prove that for all positive real numbers $x$, $x + \dfrac{1}{x} \geqslant 2$.
Structure
Assume false $\to$ deduce $\to$ contradiction $\to$ conclude.
Rational
$\dfrac{a}{b}$, integers, $b \neq 0$, simplest form.
Key lemma
$n^2$ even $\Rightarrow n$ even.
Multiples of 3
$3 \mid n^2 \Rightarrow 3 \mid n$ (check $3k\pm1$).
Primes
Product of all of them, plus $1$.
Logs
$2^p = 3^q$: even $=$ odd, impossible.
Negating "if P then Q"
P and not Q.
Parity clash
Even $=$ odd, or integer $=$ fraction.
Write the opening assumption for a proof by contradiction of each statement. (a) "$\sqrt{5}$ is irrational." (b) "If $n^3$ is odd then $n$ is odd." (c) "There is no largest multiple of $7$."
▶ Show solution
(a) Assume $\sqrt{5}$ is rational, so $\sqrt{5} = \dfrac{a}{b}$ with $a, b$ integers, $b \neq 0$, having no common factor.
(b) Assume $n^3$ is odd and $n$ is even.
(c) Assume there is a largest multiple of $7$, $M = 7k$.
Prove by contradiction that there is no greatest odd number.
▶ Show solution
Assume there is a greatest odd number, $N = 2k + 1$.
Then $N + 2 = 2(k+1) + 1$ is odd and greater than $N$.
This contradicts $N$ being the greatest, so there is no greatest odd number. $\blacksquare$
Prove that if $n^2$ is odd, then $n$ is odd.
▶ Show solution
Assume $n^2$ is odd and $n$ is even, so $n = 2k$.
Then $n^2 = 4k^2 = 2(2k^2)$, which is even.
This contradicts $n^2$ being odd, so $n$ is odd. $\blacksquare$
Prove that there are no integers $a$ and $b$ such that $10a + 15b = 7$.
▶ Show solution
Assume integers $a, b$ satisfy $10a + 15b = 7$.
Then $5(2a + 3b) = 7$, so $2a + 3b = \dfrac{7}{5}$.
The left side is an integer but $\tfrac{7}{5}$ is not — a contradiction. So no such integers exist. $\blacksquare$
Prove that $\sqrt{3}$ is irrational. You may use the result that if $n^2$ is a multiple of $3$ then $n$ is a multiple of $3$.
▶ Show solution
Assume $\sqrt{3} = \dfrac{a}{b}$ with $a, b$ integers, $b \neq 0$, and no common factor.
Then $a^2 = 3b^2$, so $a^2$ is a multiple of $3$, and hence so is $a$. Write $a = 3c$.
$9c^2 = 3b^2 \Rightarrow b^2 = 3c^2$, so $b^2$, and hence $b$, is a multiple of $3$.
So $3$ is a common factor of $a$ and $b$ — a contradiction. Hence $\sqrt{3}$ is irrational. $\blacksquare$
Prove that there are no positive integers $x$ and $y$ with $x^2 - y^2 = 1$.
▶ Show solution
Assume positive integers $x, y$ satisfy $(x - y)(x + y) = 1$.
$x + y$ is a positive integer, so $x - y$ must be positive too, and the only way two positive integers multiply to $1$ is $x + y = 1$ and $x - y = 1$.
Adding: $2x = 2$, so $x = 1$ and $y = 0$. But $y$ was positive — a contradiction.
So there are no such positive integers. $\blacksquare$
Given that $q$ is a non-zero rational number and $r$ is irrational, prove that $qr$ is irrational.
▶ Show solution
Write $q = \dfrac{a}{b}$ with $a, b$ non-zero integers.
Assume $qr$ is rational: $qr = \dfrac{c}{d}$ with $c, d$ integers, $d \neq 0$.
Then $r = \dfrac{c}{d} \div \dfrac{a}{b} = \dfrac{bc}{ad}$, and $ad \neq 0$, so $r$ is rational.
This contradicts $r$ being irrational. So $qr$ is irrational. $\blacksquare$
(Note that $q \neq 0$ is needed: $0 \times \sqrt{2} = 0$ is rational.)
Prove that $\log_3 10$ is irrational.
▶ Show solution
Assume $\log_3 10 = \dfrac{p}{q}$ with $p, q$ integers. As $\log_3 10 > 0$, take $p, q > 0$.
Then $3^{p/q} = 10$, so $3^p = 10^q$.
$3^p$ is odd, but $10^q$ (with $q \geqslant 1$) is even — a contradiction.
So $\log_3 10$ is irrational. $\blacksquare$
Prove by contradiction that for all real $x > 0$, $\;x + \dfrac{9}{x} \geqslant 6$.
▶ Show solution
Assume some $x > 0$ has $x + \dfrac{9}{x} < 6$.
Multiply by $x > 0$ (sign unchanged): $x^2 + 9 < 6x$, so $x^2 - 6x + 9 < 0$.
That is $(x - 3)^2 < 0$, impossible for real $x$ — a contradiction.
So $x + \dfrac{9}{x} \geqslant 6$ for all $x > 0$, with equality when $x = 3$. $\blacksquare$
(a) Prove that if $n$ is not a multiple of $3$ then $n^2$ leaves remainder $1$ when divided by $3$. (b) Hence prove by contradiction that there are no integers $a$ and $b$ with $a^2 = 3b + 2$. (c) Prove that $\sqrt{6}$ is irrational. (d) A student says: "$\sqrt{2}$ and $\sqrt{3}$ are irrational, and the product of two irrationals is irrational, so $\sqrt{6}$ is irrational." Show that the student's general rule is false.
▶ Show solution
(a) $n = 3k + 1 \Rightarrow n^2 = 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1$.
$n = 3k + 2 \Rightarrow n^2 = 9k^2 + 12k + 4 = 3(3k^2 + 4k + 1) + 1$. Both leave remainder $1$. $\blacksquare$
(b) Assume $a^2 = 3b + 2$. Then $a^2$ leaves remainder $2$ on division by $3$.
If $a$ is a multiple of $3$, $a^2$ leaves remainder $0$; if not, by (a) it leaves remainder $1$. Never $2$ — a contradiction. $\blacksquare$
(c) Assume $\sqrt{6} = \dfrac{a}{b}$ in simplest form. Then $a^2 = 6b^2$, so $a^2$ is even and $a$ is even: $a = 2c$.
$4c^2 = 6b^2 \Rightarrow b^2 = 2c^2$, so $b^2$ is even and $b$ is even.
Then $2$ is a common factor of $a$ and $b$ — a contradiction. So $\sqrt{6}$ is irrational. $\blacksquare$
(d) Counter-example: $\sqrt{2}$ is irrational but $\sqrt{2} \times \sqrt{2} = 2$ is rational. So "the product of two irrationals is irrational" is false, and the student's argument is not valid (even though the conclusion happens to be true).