1
$\begingroup$

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}$.

$\endgroup$
4
  • 3
    $\begingroup$ One implication is easy: if $n$ is prime, then in $\mathbb Z[i]$ we have $(c+i)^n\equiv c^n+i^n\equiv c-i\pmod n$. $\endgroup$
    – Wojowu
    Oct 25, 2020 at 10:18
  • $\begingroup$ Is there any reason to expect that $c$'s being smallest plays any role? If I drop that condition, I can take, say, an odd prime $c$ congruent to $-1$ mod $n$ by Dirichlet's theorem. So, does the test work if I just take $c=-1$? $\endgroup$ Oct 25, 2020 at 12:04
  • 1
    $\begingroup$ @EmilJeřábek No,it doesn't work...for $c=-1$ the smallest counterexample is $2047$. See here $\endgroup$
    – Pedja
    Oct 25, 2020 at 12:17
  • $\begingroup$ Ok, thanks. Then I expect the original claim not to work either. $\endgroup$ Oct 25, 2020 at 15:26

1 Answer 1

8
$\begingroup$

In other words, $z^n \equiv \bar{z}\pmod{n}$ or $z^{n+1} \equiv z\bar{z}\pmod{n}$. That splits into two conditions: $$\begin{cases} \Im z^{n+1}\equiv 0\pmod{n}, \\ (c^2+1)^{n}\equiv c^2+1\pmod{n}. \end{cases} $$

Numbers $n$ satisfying the first condition Grau et al. (2014) called Gaussian Fermat pseudoprimes to base $z$, while numbers satisfying the second condition (under the additional constraint $\gcd(c^2+1,n)=1$) are Fermat pseudoprimes to base $c^2+1$. There are many composite examples satisfying either of the two conditions, but it is hard to find those that satisfy both.

For example, Grau et al. showed that there no composite $n=4k+3$ below $10^{18}$ that are both Gaussian Fermat pseudoprimes to base $1+2I$ and Fermat pseudoprimes to base $2$.


Alternatively, it can be seen that $z^n$ can be expressed in terms on Lucas sequences: $$z^n = \frac{1}{2}V_n(P,Q) + I U_n(P,Q)$$ for $(P,Q)=(2c,c^2+1)$, and hence $n$ satisfying the two conditions is a Frobenius pseudoprime.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.