FALSE: $n^{2} + n + 41$ is prime for every natural number $n$

False claim: for every $n \in \mathbb{N}$ the integer

$\iota(n)^{2} + \iota(n) + 41$

is prime (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$), where $\iota : \mathbb{N} \to \mathbb{Z}$ is the embedding of The naturals embed in the integers and the square is the natural power of Powers $g^{n}$: natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ in the commutative monoid $(\mathbb{Z},\cdot,1)$ of $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$. As usual a numeral $k$ inside $\mathbb{Z}$ means $\iota(k)$.

Witness: $n = 40$. Here

$40^{2} + 40 + 41 \;=\; 1600 + 40 + 41 \;=\; 1681 \;=\; 41 \cdot 41 ,$

so $1681$ has the positive divisor $41$, which is neither $1$ nor $1681$: it is composite, not prime.

The failure is structural rather than accidental: $40^{2} + 40 = 40 \cdot 41$, so the whole expression is $40 \cdot 41 + 41 = 41 \cdot 41$.

• Checking small cases proves nothing here, and that is the point of the item. The values at $n = 0, 1, \dots, 39$ are classically known to be prime — this is Euler's polynomial, and the fact is not verified above, since it is not needed for a refutation. A claim that survives forty consecutive tests and fails at the forty-first is exactly the situation a universal statement has to be proved out of, not tested out of.

• The witness is not isolated. $n = 41$ fails for the same structural reason: $41^{2} + 41 + 41 = 41 \cdot (41 + 1 + 1) = 41 \cdot 43 = 1763$, again divisible by $41$ and again neither $1$ nor itself. What both cases exploit is that $41$ divides the constant term, so it divides the whole value whenever it divides $n^{2} + n$.

• The refuted claim is about $\mathbb{N}$, which contains $0$. At $n = 0$ the value is $41$, so the claim is not vacuous at its first index; the witness is needed.