Skip to main content
2 of 3
added 339 characters in body
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

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, 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.

Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152