0

Given $k = n^2 + 9n + 1$

Prove that the statement “$k$ will be a prime number for all integer values of $n$ from $1$ to $9$”, is wrong.

You can try the numbers $1$ to $9$ in turn, and determine that $6$ proves the statement wrong.

But is there an elegant mathematical way of proving the statement wrong?

Michael Hardy
  • 1
Harry B
  • 95

1 Answers1

3

One can look at the polynomial $n^2+9n+1$ modulo small primes $p$. It is never equal to $0$ modulo $2$, $3$, or $5$ (we only need to evaluate $2/3/5$ consecutive values to prove that). However, modulo $7$ the polynomial is congruent to $n^2+2n+1=(n+1)^2$, which is clearly $0\pmod7$ when $n\equiv-1\pmod7$. This shows that $n=6$ will be a counterexample (and indeed that every set of $7$ consecutive integers produces a counterexample).

Greg Martin
  • 78,820