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?

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. 


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


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

