What is the first value of $n$ for which $n^2 + n + 41$ is not a prime?

### Concept & Formula The expression given is Euler's famous prime-generating polynomial: $$P(n) = n^2 + n + 41$$ This formula is renowned for producing prime numbers for all integer values from $n = 0$ up to $n = 39$. However, it fails at the value equal to the constant term minus one. ### Step-by-Step Solution * **Analyze the Polynomial:** We need to find an $n$ where $n^2 + n + 41$ can be factored, meaning it shares a common divisor and is no longer prime. * **Test the critical value $n = 40$:** Substitute $n = 40$ into the expression: $$P(40) = 40^2 + 40 + 41$$ Factor out the common term (40) from the first two terms: $$P(40) = 40(40 + 1) + 41$$ $$P(40) = 40(41) + 41$$ Now factor out the common 41: $$P(40) = 41(40 + 1)$$ $$P(40) = 41 \times 41 = 41^2$$ * **Conclusion:** Since the result is $41^2$, the number is a perfect square and thus composite, not prime. Therefore, 40 is the first value where the formula fails. ### Exam Strategy & Shortcut You don't need to calculate large squares to solve this. Look at the constant term in the polynomial, which is 41. If you plug in $n = 41$, every term is a multiple of 41 ($41^2 + 41 + 41$), making it composite. By the same factorization logic, plugging in $n = 40$ creates $40(41) + 41$, which also factors cleanly by 41. The answer will always relate directly to the constant term. ### Common Pitfall Attempting to brute force the calculation for options (a), (b), and (c). Manually calculating and then verifying the primality of $P(10) = 151$ or $P(20) = 461$ wastes a massive amount of time. Recognize the algebraic pattern instead. ### Final Answer **Therefore, the correct answer is 40.**