# Determining if all integers of the polynomial form $n^2+21n+1$ are prime

Suppose I had a statement that said For all positive integers of n, ${n^2 + 21n + 1}$ is prime.

Attempt:

The first thing that I decided to do was to try and factor it. I immediately saw that it wasn't going to happen. This meant that the GCF for each term was one.

I then checked using the discriminant method and my result was ${\sqrt{437}}$ Though 437 is not prime since it is divisible by 19 and 23

My question is, is this enough to say that for all integers of this polynomial, ${n^2 + 21n + 1}$ is prime. If not, how else can I efficiently check to see that their exists at least one case that makes this not true.

• Can you use Wolfram Alpha? If so, try $n = 18$. – JimmyK4542 Jun 17 '15 at 5:10
• Also, the 2nd sentence here might be helpful. – JimmyK4542 Jun 17 '15 at 5:13
• I would not expect any closed form expression to always generate a prime. I think you are mistaken about factoring. If the quadratic is factorable then certainly there exists integers which will give a non-prime (i.e. a composite number), however, just because it's not factorable, doesn't mean it cannot produce composite numbers. I mean, every quadratic is "factorable" if we're allowed non-integer factors--your reasoning would suggest that this cannot create an integer value (which it obviously can). – Jared Jun 17 '15 at 5:18
• @Jared Well I didn't really make any final conclusions in regards to whether this polynomial was always prime. That is why I did 2 steps and then asked if this was enough and if not, what other steps could i employ to prove that this proposition was true or false. – Deathslice Jun 17 '15 at 5:23
• Yes, no single variable polynomial with integer coefficients can generate primes. See math.stackexchange.com/questions/304330/… – Shailesh Jun 17 '15 at 5:29

When $n=1$, our polynomial is $23$. Now evaluate it at $n=1+23$. From "failure," success!

Remark: The same basic idea can be used to show that no non-constant polynomial $P(n)$ with integer coefficients can be prime for all natural numbers $n$.

• Well besides the rudimentary plug and chug, what other techniques can I employ? – Deathslice Jun 17 '15 at 5:19
• Didn't plug and chug. After noting that $P(1)=23$, I immediately went to $n=1+23$. – André Nicolas Jun 17 '15 at 5:21
• Oh I see. Thanks for the heads up. – Deathslice Jun 17 '15 at 5:26
• @Deathslice I will add that you don't even have to evaluate. Since $24\equiv1\pmod{23}$, you also have $P(24)\equiv P(1)\pmod{23}$ for any polynomial with integer coefficients. In this case you get $P(24)\equiv0\pmod{23}$, which means that $23\mid P(24)$. (And it is easy to see that $P(24)>23$.) – Martin Sleziak Jun 17 '15 at 5:58

I would say $n^2+21n+1=(n+1)^2+19n$, so if $n+1$ has a common factor with $19$, the expression will be divisible by $19$. In fact, $18^2+21\cdot 18+1=703=19\cdot 37$

André Nicholas illustrates a general observation which is easy and which works more generally.

If you wanted to continue your own observation further, one way would be:

$$f(n)=n^2+21n+1$$

$$4f(n)=(2n+21)^2-437$$

So $f(n)$ would have a factor $437$ whenever $2n+21$ is a multiple of $437$.

And since $437=441-4=21^2-2^2=19\times 23$, $f(n)$ will have a factor $19$ whenever $2n+21$ is divisible by $19$, and $23$ whenever $2n+21$ is divisible by 23.

You just need to confirm that the relevant multiple is greater than $1\times 437, 19, 23$ most of the time.