Disproof by Counterexample

A claim with no exceptions

The claim: $n^2+n+41$n² + n + 41 is prime for every whole number n. “For every” makes it a universal statement. It claims something of each whole number, with no exceptions anywhere.

Its negation is “there is a whole number n for which $n^2+n+41$n² + n + 41 is not prime”. That is an existence claim, and an existence claim is settled by producing one such n.

Cases that fit prove nothing

Try the first few values. n = 0 gives 41, n = 1 gives 43, n = 2 gives 47, n = 3 gives 53, n = 4 gives 61 and n = 5 gives 71, all prime. In fact every value from n = 0 to n = 39 is prime, forty in a row, ending with $39^2+39+41=1601$39² + 39 + 41 = 1601.

Forty cases that fit are evidence, not a proof. The claim is about every whole number, infinitely many cases, and forty checked cases leave infinitely many unchecked.

Some of the values. Every n from 0 to 39 gives a prime, and the table shows five of them. At n = 40 the value is 41 × 41, and at n = 41 it is 41 × 43.

One case that fails

Look for an n that gives every term a common factor. At n = 41 each of the three terms is a multiple of 41: $41^2+41+41=41\left(41+1+1\right)=41\times 43$41² + 41 + 41 = 41(41 + 1 + 1) = 41 × 43. A number with the factors 41 and 43 is not prime, so n = 41 is a counterexample.

Check it in numbers: $41^2=1681$41² = 1681, and 1681 + 41 + 41 = 1763. Also 41 × 43 = 1763.

The first failure is one step earlier. At n = 40, $n^2+n=40\times 41$n² + n = 40 × 41, so $n^2+n+41=40\times 41+41=41\times 41=1681$n² + n + 41 = 40 × 41 + 41 = 41 × 41 = 1681, which is not prime either.

One is enough

One counterexample disproves the claim completely. The claim said every n gives a prime; n = 41 does not; so the claim is false. Nothing more is needed: no second counterexample, and no explanation of why the first forty values happened to be prime.

The two directions are not balanced. A claim about every case is proved only by an argument that covers every case, and it is disproved by a single case. Examples can do the disproving, never the proving.

What counts as a counterexample

A counterexample has to be a case the claim is about, and the claim has to fail there.

For “every prime is odd”, the counterexample is 2, which is prime and even. 9 and 15 are odd and not prime, so the claim says nothing about them.

For “$n^2>n$n² > n for every whole number n”, n = 1 is a counterexample: $1^2=1$1² = 1, which is not greater than 1. So is n = 0, since $0^2=0$0² = 0. At n = 2 and n = 3 the squares are 4 and 9, which are larger, so those cases fit.

For “every number that ends in 1 is prime”, 21 is a counterexample, since 21 = 3 × 7. 11 and 31 are prime, so they agree with the claim.

For a conditional, “if $a^2=b^2$a² = b², then a = b”, a counterexample must make the if-part true and the conclusion false. a = 3 and b = −3 have the same square, 9, and are not equal. a = 2 and b = 4 do not count: their squares, 4 and 16, differ, so the claim makes no promise about them.

Whole numbers above 1, with a circle for the primes and one for the odd numbers, and a sample in each region. “Every prime is odd” says that the shaded region, prime and not odd, is empty. A counterexample is a number in that region, and 2 is one. 7 fits the claim; 9 and 4 are not prime, so the claim is not about them.

The usual mistakes

Treating many fitting cases as a proof. Forty primes in a row did not make the claim true.

Offering a case outside the claim. A counterexample to “every prime is odd” must be a prime.

Offering a case that fits. 31 ends in 1 and is prime, so it agrees with the claim instead of breaking it.

Looking for more than one. A single failing case settles the claim.

A salesperson’s claim about percentages

In the application below, a salesperson claims that an agent who resolves a higher percentage of easy calls and a higher percentage of hard calls than a colleague always resolves a higher percentage of all calls. Last week’s figures for two agents are a counterexample, and a second part finds how far one count can change with the counterexample still standing.