5
$\begingroup$

Conjecture:

Let $n \in \mathbb{N}$ and $n$ odd.

Then the number $N=2^2 + n^2$ is prime, if and only if $N$ divides $2^{(N-1)/2} + 1$.

Thanks.

$\endgroup$
  • 1
    $\begingroup$ Couldn't find counterexamples up to n=10^8, might be wrong. $\endgroup$ – joro May 22 '16 at 11:33
  • 1
    $\begingroup$ the "only if" part is Fermat's little theorem $\endgroup$ – Carlo Beenakker May 22 '16 at 12:25
  • 4
    $\begingroup$ Related: mathoverflow.net/questions/234348/… $\endgroup$ – Sidney Raffer May 22 '16 at 13:04
  • 1
    $\begingroup$ No counterexamples for $n$ below $2^{32}$. In fact, below $2^{64}$ there is only one pseudoprime $N$ of the form $n^2+4$ (for $n=22047$), but it does not divive $2^{(N-1)/2}+1$. $\endgroup$ – Max Alekseyev May 22 '16 at 13:56
  • 1
    $\begingroup$ Tested all $n$ below $10^{11}$, no counterexamples found. $\endgroup$ – Max Alekseyev May 26 '16 at 15:14

Your Answer

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

Browse other questions tagged or ask your own question.