2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Can you use Wolfram Alpha? If so, try $n = 18$. $\endgroup$ – JimmyK4542 Jun 17 '15 at 5:10
  • $\begingroup$ Also, the 2nd sentence here might be helpful. $\endgroup$ – JimmyK4542 Jun 17 '15 at 5:13
  • $\begingroup$ 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). $\endgroup$ – Jared Jun 17 '15 at 5:18
  • $\begingroup$ @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. $\endgroup$ – Deathslice Jun 17 '15 at 5:23
  • 1
    $\begingroup$ Yes, no single variable polynomial with integer coefficients can generate primes. See math.stackexchange.com/questions/304330/… $\endgroup$ – Shailesh Jun 17 '15 at 5:29
6
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Well besides the rudimentary plug and chug, what other techniques can I employ? $\endgroup$ – Deathslice Jun 17 '15 at 5:19
  • $\begingroup$ Didn't plug and chug. After noting that $P(1)=23$, I immediately went to $n=1+23$. $\endgroup$ – André Nicolas Jun 17 '15 at 5:21
  • $\begingroup$ Oh I see. Thanks for the heads up. $\endgroup$ – Deathslice Jun 17 '15 at 5:26
  • $\begingroup$ @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$.) $\endgroup$ – Martin Sleziak Jun 17 '15 at 5:58
6
$\begingroup$

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$

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.