Problem 21 · AMC 8 Stretch
Core
Number Theory
intelligent-guessing-and-testinglogical-reasoning
The formula \(n^2 + n + 41\) gives a prime for \(n = 1, 2, 3, \dots, 39\). But it can't give primes forever. Find the SMALLEST positive value of \(n\) that makes \(n^2 + n + 41\) NOT prime.
Show answer
Answer: n = 40 (gives 1681 = 41 squared)
Show hints
Hint 1 of 4
A formula can spit out primes for a long time and still fail eventually. Look for an \(n\) that shares a factor with the \(41\).
Still stuck? Show hint 2 →
Hint 2 of 4
What if you choose \(n\) so that the pieces share the factor \(41\)?
Still stuck? Show hint 3 →
Hint 3 of 4
Try \(n = 41\): then \(n^2 = 41 \times 41\), \(n = 41\), and the last term is \(41\). Factor out the \(41\). But check smaller values too.
Show solution
Approach: Test cases and factor to expose a composite value
- Look for an \(n\) where the value factors. Try \(n = 40\): \(40^2 + 40 + 41 = 1600 + 40 + 41 = 1681 = 41 \times 41 = 41^2\) — a perfect square, so not prime.
- Check that nothing smaller fails: for \(n = 1\) through \(39\) the formula is known to give primes, so \(40\) is the smallest failure.
- Why it must eventually fail: at \(n = 41\), \(41^2 + 41 + 41 = 41(41 + 1 + 1) = 41 \times 43\), clearly composite.
- So the smallest \(n\) making it composite is \(40\).
Mark:
· log in to save