Skip to main content
3 of 3
Added new upper bound for verified n
Pedja
  • 2.7k
  • 15
  • 26

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 $5 \cdot 10^{11}$.

Pedja
  • 2.7k
  • 15
  • 26