2
$\begingroup$

$p$ is an odd prime and $k$ is a positive integer. Let $n=k \cdot p^2+1$. If $2^k \not\equiv 1 \pmod n$ and $2^{n-1} \equiv 1 \pmod n$, is $n$ prime? If it is, why?

  • 8
    What do you think?2012-05-28
  • 1
    Also posted to MathOverflow, http://mathoverflow.net/questions/98222/prime-of-the-form-nkp21, without any mention of the post here.2012-05-29
  • 0
    I don't see any reason why this should always be true. Are there infinitely many base-2 pseudoprimes of the form $p^2+1$, or $2p^2+1$? - these would be counterexamples. I suspect the reason it's hard to find a counterexample is just because base-2 pseudoprimes are somewhat rare.2012-05-29

2 Answers 2