$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?
Is $n = k \cdot p^2 + 1$ necessarily prime if $2^k \not\equiv 1 \pmod{n}$ and $2^{n-1} \equiv 1 \pmod{n}$?
2
$\begingroup$
number-theory
prime-numbers
-
8What do you think? – 2012-05-28
-
1Also posted to MathOverflow, http://mathoverflow.net/questions/98222/prime-of-the-form-nkp21, without any mention of the post here. – 2012-05-29
-
0I 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