Proof by Contradiction and Counterexample

Some statements are hard to prove head-on. How could you directly show that $\sqrt{2}$ can never be written as a fraction, when there are infinitely many fractions to rule out? Proof by contradiction takes a sneaky route: suppose the statement is false, and show that this leads to something impossible. And when a statement is false, you don’t need a proof at all, just one example where it fails: a counterexample.

Key ideas

How proof by contradiction works

To prove a statement $S$:

1. Assume the opposite: suppose $S$ is false.
2. Reason logically from that assumption, using correct steps.
3. Reach a contradiction: something that can’t be true, like $1 = 0$, or a number that is both odd and even, or a fraction in lowest terms that can still be simplified.
4. Conclude: the assumption must be wrong, so $S$ is true.

Here’s a short example. Claim: there is no largest even number.

Suppose, for a contradiction, that there is a largest even number; call it $N$. Then $N = 2m$ for some integer $m$. But $N + 2 = 2(m + 1)$ is also even, and $N + 2 \gt N$. So $N$ is not the largest even number, which contradicts our assumption. Therefore there is no largest even number. $\blacksquare$

Useful facts for irrationality proofs

A number is rational if it can be written as $\dfrac{p}{q}$ where $p$ and $q$ are integers and $q \ne 0$ (see number systems). Every rational number can be written in lowest terms, where $p$ and $q$ have no common factor other than $1$. Irrationality proofs use this.

You’ll also need this fact: if $p^2$ is even, then $p$ is even. Why: if $p$ were odd, $p = 2n + 1$, then $p^2 = 4n^2 + 4n + 1 = 2(2n^2 + 2n) + 1$ would be odd. The same reasoning works for cubes: if $p^3$ is even, then $p$ is even.

Disproving with a counterexample

A statement that claims something is true for all cases is false if there is even one case where it fails. That case is a counterexample.

It is not enough to just state the counterexample. You must show why it is one: substitute it in and explain why the statement fails for it.

For example, the claim ”$x^2 \ge x$ for every real number $x$” is false. Take $x = \tfrac{1}{2}$: then $x^2 = \tfrac{1}{4}$, and $\tfrac{1}{4} \lt \tfrac{1}{2}$, so $x^2 \ge x$ is not true for this value.

Notice the asymmetry: one counterexample disproves a “for all” statement, but no number of examples can prove one.

Which method should you use?

The statement…	Try…
can be reached directly with algebra (an identity, a result about $2n$ or $2n + 1$)	a deductive proof
is about every positive integer $n$, and case $k + 1$ builds on case $k$ (sums, divisibility, $n$th derivatives)	proof by induction
says something is impossible or not true: “is irrational”, “there is no largest…”, “there are infinitely many…”, “has no solutions”	proof by contradiction
claims to be true “for all” cases, but you suspect it’s false	look for a counterexample

Worked examples

Example 1: Counterexamples

Show that each statement is not always true.

• (a) “For every positive integer $n$, $2^n + 1$ is prime.”
• (b) “If $a \gt b$, then $a^2 \gt b^2$.”

Solution.

(a) Take $n = 3$: $2^3 + 1 = 9 = 3 \times 3$. Since $9$ has the factor $3$, it is not prime. So the statement is false for $n = 3$, and it is not true for every positive integer.

(b) Take $a = 1$ and $b = -2$. Then $a \gt b$, since $1 \gt -2$. But $a^2 = 1$ and $b^2 = 4$, so $a^2 \lt b^2$. The statement is false for these values.

In both parts, the explanation (why $9$ isn’t prime, why $1 \lt 4$ breaks the claim) is what earns the marks.

Example 2: √2 is irrational

Prove that $\sqrt{2}$ is irrational.

Solution. Suppose, for a contradiction, that $\sqrt{2}$ is rational. Then

$$\sqrt{2} = \frac{p}{q}$$

where $p$ and $q$ are positive integers with no common factor (the fraction is in lowest terms). Square both sides and rearrange:

$$2 = \frac{p^2}{q^2} \quad\Rightarrow\quad p^2 = 2q^2$$

So $p^2$ is even, which means $p$ is even. Write $p = 2m$ for some integer $m$:

$$(2m)^2 = 2q^2 \quad\Rightarrow\quad 4m^2 = 2q^2 \quad\Rightarrow\quad q^2 = 2m^2$$

So $q^2$ is even, which means $q$ is even.

Now $p$ and $q$ are both even, so they have a common factor of $2$. This contradicts the assumption that $\dfrac{p}{q}$ was in lowest terms. Therefore $\sqrt{2}$ is irrational. $\blacksquare$

Example 3: log₂3 is irrational

Prove that $\log_2 3$ is irrational.

Solution. Suppose, for a contradiction, that $\log_2 3$ is rational. Since $3 \gt 1$, $\log_2 3 \gt 0$, so we can write

$$\log_2 3 = \frac{p}{q}$$

where $p$ and $q$ are positive integers. By the definition of a logarithm,

$$2^{p/q} = 3 \quad\Rightarrow\quad \left(2^{p/q}\right)^q = 3^q \quad\Rightarrow\quad 2^p = 3^q$$

Since $p \ge 1$, $2^p$ is even. But $3^q$ is a product of odd numbers, so it is odd. An even number can’t equal an odd number, which is a contradiction. Therefore $\log_2 3$ is irrational. $\blacksquare$

The step ”$p$ and $q$ are positive” matters: if $p$ were $0$, then $2^p = 1$ would be odd, and the argument would fall apart.

Example 4: There are infinitely many primes

Prove that there are infinitely many prime numbers.

Solution. This proof goes back to Euclid, about 2300 years ago.

Suppose, for a contradiction, that there are only finitely many primes. List all of them: $p_1, p_2, p_3, \dots, p_k$. Now build the number

$$N = p_1 \times p_2 \times p_3 \times \dots \times p_k + 1$$

$N$ is bigger than $1$, so it has at least one prime factor. That prime must be one of $p_1, p_2, \dots, p_k$, since the list contains every prime. But dividing $N$ by any $p_i$ leaves a remainder of $1$, because $N$ is one more than a multiple of $p_i$. So none of the primes in the list divides $N$.

That means $N$ has a prime factor that isn’t on the list, which contradicts the assumption that the list contained every prime. Therefore there are infinitely many primes. $\blacksquare$

Careful: the proof does not say $N$ itself is prime. For example, $2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30031 = 59 \times 509$. What it says is that $N$ has a prime factor missing from the list.

Common mistakes

Stating a counterexample without explaining it. Writing "$n = 3$" isn’t enough. Show the calculation ($2^3 + 1 = 9 = 3 \times 3$) and say why it breaks the statement (it isn’t prime).

Trying to prove a “for all” statement with examples. Checking $\sqrt{2} \ne \tfrac{7}{5}$, $\sqrt{2} \ne \tfrac{17}{12}$, and so on doesn’t prove $\sqrt{2}$ is irrational. There are infinitely many fractions; you need a proof.

Forgetting “in lowest terms”. The contradiction in the $\sqrt{2}$ proof comes from $p$ and $q$ both being even. That’s only a contradiction if you said at the start that $\dfrac{p}{q}$ has no common factor.

Thinking Euclid’s N must be prime. $N = p_1 p_2 \cdots p_k + 1$ is not always prime ($30031 = 59 \times 509$). The proof only needs $N$ to have a prime factor that isn’t on the list.

Skipping the reason that p is even. ”$p^2$ is even, so $p$ is even” needs a justification the first time you use it: if $p$ were odd, $p^2$ would be odd.

Not saying what was contradicted. End by naming the contradiction (“this contradicts $\dfrac{p}{q}$ being in lowest terms”) and stating the conclusion (“so $\sqrt{2}$ is irrational”).

Practice

1. (Warm-up) Find a counterexample to show that this statement is false: “If $a^2 \gt b^2$, then $a \gt b$.”

Solution

Take $a = -3$ and $b = 1$. Then $a^2 = 9$ and $b^2 = 1$, so $a^2 \gt b^2$. But $a = -3 \lt 1 = b$, so $a \gt b$ is false. The statement fails for these values.

(Any negative $a$ with $|a| \gt |b|$ works.)

2. (Warm-up) Find a counterexample to show that this statement is false: “The sum of two irrational numbers is always irrational.”

Solution

Take $\sqrt{2}$ and $-\sqrt{2}$. Both are irrational ($-\sqrt{2}$ is irrational because if it equalled a fraction $\dfrac{p}{q}$, then $\sqrt{2}$ would equal $\dfrac{-p}{q}$). But

$$\sqrt{2} + \left(-\sqrt{2}\right) = 0 = \frac{0}{1}$$

which is rational. So the sum of two irrational numbers is not always irrational.

3. (Warm-up) Prove by contradiction that there is no smallest positive rational number.

Solution

Suppose, for a contradiction, that there is a smallest positive rational number, $q$. Then $\dfrac{q}{2}$ is also rational (if $q = \dfrac{a}{b}$, then $\dfrac{q}{2} = \dfrac{a}{2b}$), it is positive, and $\dfrac{q}{2} \lt q$. So $q$ is not the smallest positive rational number, which contradicts the assumption. Therefore there is no smallest positive rational number. $\blacksquare$

4. (Core) Prove that $\sqrt{3}$ is irrational. You may use the fact that if $p^2$ is a multiple of $3$, then $p$ is a multiple of $3$.

Solution

Suppose, for a contradiction, that $\sqrt{3} = \dfrac{p}{q}$ where $p$ and $q$ are positive integers with no common factor. Then

$$3 = \frac{p^2}{q^2} \quad\Rightarrow\quad p^2 = 3q^2$$

so $p^2$ is a multiple of $3$, and therefore $p$ is a multiple of $3$. Write $p = 3m$:

$$9m^2 = 3q^2 \quad\Rightarrow\quad q^2 = 3m^2$$

so $q^2$ is a multiple of $3$, and therefore $q$ is a multiple of $3$.

Now $p$ and $q$ have a common factor of $3$, contradicting the assumption that $\dfrac{p}{q}$ is in lowest terms. Therefore $\sqrt{3}$ is irrational. $\blacksquare$

(Why the given fact is true: if $p$ is not a multiple of $3$, then $p = 3n + 1$ or $p = 3n + 2$, and $p^2 = 9n^2 + 6n + 1$ or $9n^2 + 12n + 4 = 3(3n^2 + 4n + 1) + 1$. Either way, $p^2$ leaves a remainder of $1$ when divided by $3$.)

5. (Core) Let $a$ be a rational number and $b$ an irrational number. Prove by contradiction that $a + b$ is irrational.

Solution

Suppose, for a contradiction, that $a + b$ is rational. Write $a = \dfrac{m}{n}$ and $a + b = \dfrac{p}{q}$, where $m, n, p, q$ are integers and $n, q \ne 0$. Then

$$b = (a + b) - a = \frac{p}{q} - \frac{m}{n} = \frac{pn - mq}{qn}$$

Here $pn - mq$ and $qn$ are integers, and $qn \ne 0$, so $b$ is rational. This contradicts $b$ being irrational. Therefore $a + b$ is irrational. $\blacksquare$

6. (Core) Prove that $\log_3 5$ is irrational.

Solution

Suppose, for a contradiction, that $\log_3 5$ is rational. Since $5 \gt 1$, $\log_3 5 \gt 0$, so $\log_3 5 = \dfrac{p}{q}$ with $p$ and $q$ positive integers. Then

$$3^{p/q} = 5 \quad\Rightarrow\quad 3^p = 5^q$$

Since $p \ge 1$, $3^p$ is a multiple of $3$. But $5^q$ is a product of $5$‘s, and $3$ is prime and doesn’t divide $5$, so $5^q$ is not a multiple of $3$. This is a contradiction. Therefore $\log_3 5$ is irrational. $\blacksquare$

7. (Core) Show that this statement is false: “For every positive integer $n$, $n^2 + 3n + 1$ is prime.”

Solution

Try values in turn: $n = 1, 2, 3, 4, 5$ give $5, 11, 19, 29, 41$, which are all prime. But for $n = 6$:

$$6^2 + 3(6) + 1 = 36 + 18 + 1 = 55 = 5 \times 11$$

$55$ is not prime, so $n = 6$ is a counterexample, and the statement is false.

8. (Challenge) Prove that $\sqrt[3]{2}$ is irrational.

Solution

Suppose, for a contradiction, that $\sqrt[3]{2} = \dfrac{p}{q}$ where $p$ and $q$ are positive integers with no common factor. Cube both sides:

$$2 = \frac{p^3}{q^3} \quad\Rightarrow\quad p^3 = 2q^3$$

So $p^3$ is even. Then $p$ must be even (if $p$ were odd, $p^3$ would be a product of odd numbers, so odd). Write $p = 2m$:

$$8m^3 = 2q^3 \quad\Rightarrow\quad q^3 = 4m^3 = 2(2m^3)$$

So $q^3$ is even, and by the same reasoning $q$ is even.

Now $p$ and $q$ are both even, contradicting the assumption that $\dfrac{p}{q}$ is in lowest terms. Therefore $\sqrt[3]{2}$ is irrational. $\blacksquare$

9. (Challenge) Prove by contradiction that there are no integers $x$ and $y$ with $x^2 - y^2 = 6$.

Solution

Suppose, for a contradiction, that there are integers $x$ and $y$ with $x^2 - y^2 = 6$. Factor:

$$(x - y)(x + y) = 6$$

The two factors $x - y$ and $x + y$ differ by $2y$, which is even, so they are both even or both odd.

• If both are odd, their product is odd. But $6$ is even. Contradiction.
• If both are even, each is a multiple of $2$, so their product is a multiple of $4$. But $6$ is not a multiple of $4$. Contradiction.

Either way we reach a contradiction, so there are no integers $x$ and $y$ with $x^2 - y^2 = 6$. $\blacksquare$