3.4 Disproofs

The idea of a “disproof” is really just semantics — in order to disprove a statement we need to prove its negation.

So far we’ve been discussing proofs quite a bit but have paid very little attention to a really huge issue. If the statements we are attempting to prove are false, no proof is ever going to be possible. Really, a prerequisite to developing a facility with proofs is developing a good “lie detector.” We need to be able to guess, or quickly ascertain, whether a statement is true or false. If we are given a universally quantified statement, the first thing to do is try it out for some random elements of the universe we’re working in. If we happen across a value that satisfies the statement’s hypotheses but doesn’t satisfy the conclusion, we’ve found what is known as a counterexample.

Consider the following statement about integers and divisibility:

Conjecture 3.1 $$\forall a,b,c \in {\mathbb Z}, \; a \!\mid\!bc \; \implies \; a \!\mid\!b \, \lor \, a \!\mid\!c.$$

This is phrased as a UCS, so the hypothesis is clear. We’re looking for three integers so that the first divides the product of the other two. In the following table, we have collected several values for $a$, $b$ and $c$ such that $a \!\mid\!bc$.

$$\begin{array}{c|c|c|c} a & b & c & a \!\mid\!b \, \lor \, a \!\mid\!c ? \\ \hline 2 & 7 & 6 & \text{yes} \\ 2 & 4 & 5 & \text{yes} \\ 3 & 12 & 11 & \text{yes} \\ 3 & 5 & 15 & \text{yes} \\ 5 & 4 & 15 & \text{yes} \\ 5 & 10 & 3 & \text{yes} \\ 7 & 2 & 14 & \text{yes} \\ \end{array}$$

Exercise 3.5 As noted in Section 1.2, the statement above is related to whether or not $a$ is prime. Note that in the table, only prime values of $a$ appear. This is a rather broad hint. Find a counterexample to Conjecture 3.1.

There can be times when the search for a counterexample starts to feel really futile. Would you think it likely that a statement about natural numbers could be true for (more than) the first 50 numbers and yet still be false?

Exercise 3.6 Find a counterexample to the following statement: $$\forall n \in {\mathbb Z}^+, \; n^2 - 79n + 1601 \, \mbox{is prime.}$$

Hidden within Euclid’s proof of the infinitude of the primes is a sequence. Recall that in the proof, we deduced a contradiction by considering the number $N$ defined by

$$N = 1 + \prod_{k=1}^n p_k.$$

Define a sequence by

$$N_n = 1 + \prod_{k=1}^n p_k,$$

where $\{p_1, p_2, \ldots , p_n\}$ are the actual first $n$ primes. The first several values of this sequence are: $$\begin{array}{c|c} n & N_n \\ \hline 1 & 1+(2) = 3 \\ 2 & 1+(2\cdot 3) = 7\\ 3 & 1+(2\cdot 3\cdot 5) = 31\\ 4 & 1+(2\cdot 3\cdot 5\cdot 7) = 211\\ 5 & 1+(2\cdot 3\cdot 5\cdot 7\cdot 11) = 2311\\ \vdots & \vdots \\ \end{array}$$

In the proof, we deduced a contradiction by noting that $N_n$ is much larger than $p_n$. So if $p_n$ is the largest prime, it follows that $N_n$ can’t be prime — but what really appears to be the case (just look at that table!) is that $N_n$ actually is prime for all $n$.

Exercise 3.7 Find a counterexample to the conjecture that $1+\prod\limits_{k=1}^n p_k$ is itself always a prime.

3.4.1 Exercises

1. Find a polynomial that assumes only prime values for a reasonably large range of inputs.

2. Find a counterexample to the conjecture that $\forall a,b,c \in {\mathbb Z}, a \!\mid\!bc \; \implies \; a \!\mid\!b \, \lor \, a \!\mid\!c$ using only powers of 2.

3. The alternating sum of factorials provides an interesting example of a sequence of integers. $$\begin{gather*} 1! = 1 \\ 2! - 1! = 1\\ 3! - 2! + 1! = 5 \\ 4! - 3! + 2! - 1! = 19 \\ \text{etc.} \end{gather*}$$ Are they all prime? (After the first two 1’s.)

4. It has been conjectured that whenever $p$ is prime, $2^p - 1$ is also prime. Find a minimal counterexample.

5. True or false: The sum of any two irrational numbers is irrational. Prove your answer.

6. True or false: There are two irrational numbers whose sum is rational. Prove your answer.

7. True or false: The product of any two irrational numbers is irrational. Prove your answer.

8. True or false: There are two irrational numbers whose product is rational. Prove your answer.

9. True or false: Whenever an integer $n$ is a divisor of the square of an integer, $m^2$, it follows that $n$ is a divisor of $m$ as well. (In symbols, $\forall n \in {\mathbb Z}, \forall m \in {\mathbb Z}, n \!\mid\!m^2 \; \implies \; n \!\mid\!m$ .) Prove your answer.

10. In an exercise in Section 3.2, we proved that the quadratic equation $ax^2 + bx + c = 0$ has two solutions if $ac < 0$. Find a counterexample which shows that this implication cannot be replaced with a biconditional.