Math Detours · Grade 9 · Around the corner · 2

One counterexample is enough

n² + n + 41 is prime for n = 0, 1, 2, … 39. Forty cases are not a proof, and n = 40 is why.

Name ____________________Date ____________

Tonight's idea

Put whole numbers into \(n^2 + n + 41\). Starting from \(n = 0\) you get 41, 43, 47, 53, 61, 71, … Each is prime: no divisors except 1 and itself. It stays that way from \(n = 0\) all the way to \(n = 39\). Forty primes in a row. So is it always prime? Try \(n = 40\):

\[40^2 + 40 + 41 = 40(40 + 1) + 41 = 40 \times 41 + 41 = 41 \times 41.\]

Not prime. Forty successes were evidence, not proof.

A claim about every number is sunk by one case where it fails. That case is a counterexample. No pile of successes can prove such a claim. Only a reason that covers every case can.

Here is another trap. Mark points on a circle and join every pair with a straight line. Place the points so that no three chords meet at one point inside the circle. Count the regions.

1 point 1 2 points 2 3 points 4 4 points 8 5 points 16 6 points 31
Regions: 1, 2, 4, 8, 16. Doubling, surely. Then six points give 31, not 32. Why: each new chord adds one region, plus one for every chord it crosses. There are \(\binom62 = 15\) chords, and every 4 of the points give exactly one crossing, \(\binom64 = 15\) of them. So \(1 + 15 + 15 = 31\).

Watch one: Fermat's guess

Fermat studied the numbers \(2^{2^n} + 1\), where the exponent is itself a power of 2.

\(n = 0, 1, 2, 3, 4\) give \(3,\ 5,\ 17,\ 257,\ 65537\). All prime. He guessed that every number of this kind is prime.

\(n = 5\) gives \(2^{32} + 1 = 4294967297\), too big to test easily by hand. Euler later found

\[4294967297 = 641 \times 6700417.\]

One counterexample, and the guess was finished. Nobody has found another prime of this kind since.

Your turn

  1. Find a counterexample to each claim. (a) Every prime number is odd. (b) Squaring a number never makes it smaller. (c) If a whole number divides by 4 and by 6, it divides by 24.
  2. Look at \(n^2 - n + 11\). (a) Work it out for \(n = 1, 2, 3, 4, 5\). Are the answers prime? (b) Without more calculating, name a value of \(n\) for which it is certainly not prime, and say why.
  3. Claim: "if \(p\) is prime, then \(2^p - 1\) is prime." (a) Check it for \(p = 2, 3, 5, 7\). (b) For \(p = 11\) you get 2047. Divide 2047 by 23. What does that do to the claim?
  4. Each claim is about every whole number \(n\). If it is false, give a counterexample. If it is true, give a reason that covers every \(n\). (a) \(n^2 + n\) is even. (b) The sum of three whole numbers in a row is odd. (c) \(n^2 + n + 41\) is odd.

Stretch: no formula of this shape works

Replace 41 by any whole number \(c\) bigger than 1. Show that \(n^2 + n + c\) cannot be prime for every whole number \(n\). Hint: try \(n = c\) and factor what you get.

Answers

  1. (a) 2 is prime and even. (b) \(\left(\tfrac12\right)^2 = \tfrac14\), which is smaller than \(\tfrac12\). Any number between 0 and 1 works. (c) 12 divides by 4 and by 6 but not by 24. So does 36.
  2. (a) 11, 13, 17, 23, 31. All prime. (b) \(n = 11\): \(11^2 - 11 + 11 = 11^2 = 121\), which divides by 11. (In fact it is prime for every \(n\) from 0 to 10, then fails.)
  3. (a) 3, 7, 31, 127. All prime. (b) \(2047 = 23 \times 89\), so it is not prime. 11 is prime, so the claim is false. Four successes and one failure make a false claim.
  4. (a) True. \(n^2 + n = n(n + 1)\), two whole numbers in a row. One of them is even, so the product is even. (b) False. \(1 + 2 + 3 = 6\). (c) True. By (a), \(n^2 + n\) is even, and an even number plus 41 is odd. Notice that "always odd" is true while "always prime" is false.

Stretch. Put \(n = c\): \(c^2 + c + c = c^2 + 2c = c(c + 2)\). Both factors are bigger than 1, so this is not prime. For \(c = 41\) that is \(n = 41\), giving \(41 \times 43 = 1763\): the formula fails a second time straight after \(n = 40\).

← PreviousNext: Why n³ − n always divides by 6 →