We know that if $q=4k+3$ ($q$ is a prime), then $(a+bi)^q=abi \pmod q$ for every Gaussian integer $a+bi$. Now consider a composite number $N=4k+3$ that satisfies this condition for the case $a+bi=3+2i$. I use Mathematica 8 and find no solution less than $5\cdot 10^7$. Can someone find a larger number for the condition, and can this be used for a primality test?

$\begingroup$ How do you prove the statement in the first sentence? $\endgroup$ – Igor Rivin Dec 2 '12 at 5:45

$\begingroup$ @Igor: it looks like wsc810 was answering your question, not the OP's. You could also say that for $q = 3 mod 4$, both the Frobenius $x \mapsto x^q$ and the map $i \mapsto i$ induce the unique nontrivial field automorphism on $\mathbb{Z}[i]/q \cong \mathbb{F}_{q^2}$, hence coincide. $\endgroup$ – Todd Trimble♦ Dec 2 '12 at 12:39

3$\begingroup$ Search for Frobenius pseudoprimes. $\endgroup$ – Felipe Voloch Dec 2 '12 at 16:10

1$\begingroup$ Possibly helpful reference on Frobenius pseudoprimes : MR1680879 (2001g:11191) Grantham, Jon . Frobenius pseudoprimes. Math. Comp. 70 (2001), no. 234, 873891 ams.org/journals/mcom/200170234/S0025571800011972/… $\endgroup$ – François Brunault Dec 3 '12 at 9:14
This looks sort of interesting. I don't have an answer, but just a few observations. Instead of restricting to $3 + 2i$, we might consider the same condition holding for every $\alpha = a + bi$ prime to $N$, i.e., such that
$$\alpha^N \equiv \bar{\alpha} \pmod N.$$
We are then led to consider a Gaussian analogue of Carmichael numbers, i.e., Carmichael ideals for the Gaussian integers, generated by numbers $N$ of the particular form $N = q_1 q_2\ldots q_k$ where $q_i \equiv 3\pmod 4$ for $i = 1, \ldots, k$.
These will be ordinary Carmichael numbers $N$ but with the extra condition that
$$(q_i^2  1)\; \; N^21$$
for $i = 1, \ldots, k$. For example, the ordinary Carmichael number $7 \cdot 19 \cdot 67 = 8911$ fails to meet this stronger condition.
I expect these stronger Carmichael numbers exist, but as I say I don't have an example. If I were researching this problem myself, I would try to get hold of a table of Carmichael numbers, see which ones have all of its prime factors $q_i$ congruent to 3 modulo 4, and then test the condition $q_i^2  1 \; \; N^21$ on those.

$\begingroup$ Hm, is it possible that your condition implies the number is Carmichael? $\endgroup$ – joro Dec 3 '12 at 6:24

$\begingroup$ I thought it did imply that. For any $\alpha \in \mathbb{Z}$, we have $\alpha^N \equiv \bar{\alpha} = \alpha \; \pmod N$. $\endgroup$ – Todd Trimble♦ Dec 3 '12 at 12:11

1$\begingroup$ I vaguely remember seeing existence of your condition as an open problem, can't find the paper. Maybe wrong and have seen something similar though. $\endgroup$ – joro Dec 3 '12 at 15:39
As Mr. R. Gerbicz pointed out in the mersenne forum an eventual counterexample for the base 3+2i must be 13PRP (just multiply the equation with its conjugate). The first point to check is to make a list of pseudoprimes base 13 which are 3 (mod 4). I checked them to 10^10 and there is no counterexample which pass this test (a couple of them which are 1 (mod 4) passes the complex base test, but none of the 3 (mod 4)). However, the general opinion is that this test is a "hidden" multibase PRP test, or a (n1)(n+1) combined test, and as Mr. Tom Womack pointed out in that thread, if a couterexample exists, it must be HIGH (somewhere in 10^30 or so).
now we see under what conditions,$(a+bI)^N=abI\pmod q$,
we can conclude N dosent have $4k+1$ factors, suppose there is a factor $q=4k+1$ for $N$and$N=q*d$,$d=4k+3$
then $(a+bI)^N=((a+bI)^q)^d=(a+bI)^d=a^d+b^d(I)^{4k+3}=a^db^d*I\pmod q$.
so N dosent have $4k+1$ factors.
and There are 3,or 5 or 7 etc.factors of form 4k+3 for N.
now to the 3 factors.
Suppose N exists. $(a+bI)^{q_1q_2q_3}=abI\pmod {q_1q_2q_3}$
$((a+bI)^{q_1})^{q_2q_3}=((abI)^{q_2q_3}=abI\pmod {q_1}$
$((a+bI)^{q_2})^{q_1q_3}=((abI)^{q_1q_3}=abI\pmod {q_2}$
$((a+bI)^{q_3})^{q_1q_2}=((abI)^{q_1q_2}=abI\pmod {q_3}$
as$((abI)^{(q_1+1)})^{(q_11)k_1}=(a^2+b^2)^{(q_11)k_1}=1\pmod {q_1}$
multiply (abI) to the both sides.
$(abI)((abI)^{(q_1+1)})^{(q_11)*k_1}=(abI)^{(q_1^21)*k_1+1}\pmod {q_1}$
$(abI)((abI)^{(q_2+1)})^{(q_21)*k_2}=(abI)^{(q_2^21)*k_2+1}\pmod {q_2}$
$(abI)((abI)^{(q_3+1)})^{(q_31)*k_3}=(abI)^{(q_3^21)*k_3+1}\pmod {q_3}$
so we have
$q_2q_3=(q_1^21)*k_1+1$ (1)
$q_1q_3=(q_2^21)*k_2+1$ (2)
$q_1q_2=(q_3^21)*k_3+1$ (3)
(1)/(2)
$\frac{q_2}{q_1}=\frac{(q_1^21)*k_1+1}{(q_2^21)*k_2+1}$
introduce variable $t$ and it must be a integer.
$(q_1^21)k_1+1=q_2t$ (4)
$(q_2^21)k_2+1=q_1t$ (5)
tanspose
$(q_1^21)k_1=q_2t1$ (6)
$(q_2^21)k_2=q_1t1$ (7)
(6)*(7)
$q_1q_2t^2(q_1+q_2)t+1(q_1^21)(q_2^21)k_1k_2=0$
$\Delta=(q_1+q_2)^24q_1q_2(1(q_1^21)(q_2^21)k_1k_2)$
$=(q_1q_2)^2+4q_1q_2(q_1^21)(q_2^21)k_1k_2$
$t=\frac{(q_1+q_2)\pm\sqrt{(q_1q_2)^2+4q_1q_2(q_1^21)(q_2^21)k_1k_2}}{2q_1q_2}$
$(q_1+q_2)\pm\sqrt{\Delta}=(q_1+q_2)\pm(q_1q_2)\ne 0\pmod {q_1q_2}$
so $t$ does not exist. therefore the Compsite Number for $N=4k+3$ dose not exist.

$\begingroup$ we can still deal with for five factors. so there isn't any composite number sastifies the conditions. $\endgroup$ – wanglei Dec 3 '12 at 9:48

$\begingroup$ if q=4k+1 and prime, then (a+bi)^q is (a+bi) and NOT (abi). the "" is only for prime q=4k+3. your proof is wrong from the start, please recheck it. $\endgroup$ – user29817 Dec 20 '12 at 7:10