Hunting for a counterexample
Claims like “for every n the number is prime” look true on the first checks — and break later. Find the smallest n for which the claim is false.
How to solve it
To prove a claim “for every $n$” you need an argument. To refute it, one example where it fails is enough. Such an example is called a counterexample. Here you look for one, and for the smallest one.
Step by step
- Try $n$ in order: $1, 2, 3, \dots$ (or from the number the claim starts with).
- For each value check the claim. To check whether a number is prime, divide it by the primes $2, 3, 5, 7, \dots$ until the square of the divisor exceeds the number.
- Look for a shortcut: if the expression factors for some $n$, that is a counterexample. For example, $n^2 + n + 41$ at $n = 41$ is divisible by $41$.
- The first $n$ for which the claim fails is the answer.
Common mistakes
- Checking a few first values and deciding the claim is true. The formula $n^2 + n + 41$ gives primes for every $n$ from $0$ to $39$ and breaks only at $n = 40$.
- Skipping values: the counterexample found is not the smallest one.
- Calling a number prime when it has a large prime factor: $221 = 13 \cdot 17$, $1001 = 7 \cdot 11 \cdot 13$. Try divisors up to the square root.
- Forgetting that $1$ is not a prime.