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

Improve this question
$\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
    Commented 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$
    – Emil Jeřábek
    Commented 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
    Commented Oct 25, 2020 at 12:17
  • $\begingroup$ Ok, thanks. Then I expect the original claim not to work either. $\endgroup$
    – Emil Jeřábek
    Commented Oct 25, 2020 at 15:26

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .