Skip to main content
2 of 3
a superfluous "odd"
Wlod AA
  • 4.8k
  • 17
  • 23

Primality test for numbers of the form $4k+3$

Can you prove or disprove the following claim:

Let $n$ be a natural number of the form $4k+3$ , and let $c$ be the smallest odd prime such that $\binom{c}{n}=-1$ , where $\binom{}{}$ denotes a Jacobi symbol. Let $z=c+i$ be a complex number , then $n$ is prime iff $\text{Re}\left(z^n\right) \equiv c \pmod n$ and $\text{Im}\left(z^n\right) \equiv -1 \pmod n $ .

You can run this test here. I have verified this claim for all $n$ up to $10^{10}$.

Pedja
  • 2.7k
  • 15
  • 26