How can I find the number of primes of the form $|n^2 - 6n + 5|$ where $n$ is an integer? Through trial and error, I have found $n = 6$ (this one is obvious), and $2$. Are there any more, and what is a smarter way to solve this question?

  • 3
    $\begingroup$ I think $|(n-1)(n-5)|$ is prime if either $|n-1| = 1$ or $|n-5| = 1$. $\endgroup$ – GAVD Aug 19 '15 at 6:55
  • 1
    $\begingroup$ I would say that the comment by Andre Nicolas is your answer. One of the factors must equal 1, and the other factor must be a prime. $\endgroup$ – DanielWainfleet Aug 19 '15 at 7:07

The first thing I did when I saw your question was compute about a dozen values for small $n$ and look them up in the OEIS, which gave me A028347 and the formula $n^2 - 4$. Clearly for $n^2 - 4$ to be prime you need $n$ to be odd. Slightly less obvious, you need for $n$ to be a multiple of 3, because otherwise $n^2 \equiv 1 \pmod 3$. These conditions are necessary but not sufficient.

Digging a little further, we find that $n^2 - 4 = (n - 2)(n + 2)$: this is clearest when the formula gives you semiprimes with prime factors 4 apart, e.g., $19 \times 23$, $37 \times 41$, $43 \times 47$.

So you have found all the prime values already.

| cite | improve this answer | |
  • 2
    $\begingroup$ Do note that the equation $n^2 - 6n + 5$ has a different "offset" (to use OEIS parlance) from $n^2 - 4$. In fact, to properly make the latter exactly equivalent to the former you need to change it to $(n - 3)^2 - 4$. Very minor detail, though. $\endgroup$ – John-Luke Aug 19 '15 at 21:59
  • $\begingroup$ Yes, thank you for pointing that out. $\endgroup$ – Robert Soupe Aug 20 '15 at 1:00

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.