Is there a composite number that satisfies these conditions?

Question

We know that if $q=4k+3$ ($q$ is a prime), then $(a+bi)^q=a-bi \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?

Answer 1

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^2-1$$

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^2-1$ on those.

Answer 2

As Mr. R. Gerbicz pointed out in the mersenne forum an eventual counterexample for the base 3+2i must be 13-PRP (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" multi-base PRP test, or a (n-1)(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).

Answer 3

now we see under what conditions,$(a+bI)^N=a-bI\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^d-b^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}=a-bI\pmod {q_1q_2q_3}$
$((a+bI)^{q_1})^{q_2q_3}=((a-bI)^{q_2q_3}=a-bI\pmod {q_1}$
$((a+bI)^{q_2})^{q_1q_3}=((a-bI)^{q_1q_3}=a-bI\pmod {q_2}$
$((a+bI)^{q_3})^{q_1q_2}=((a-bI)^{q_1q_2}=a-bI\pmod {q_3}$
as$((a-bI)^{(q_1+1)})^{(q_1-1)k_1}=(a^2+b^2)^{(q_1-1)k_1}=1\pmod {q_1}$
multiply (a-bI) to the both sides.
$(a-bI)((a-bI)^{(q_1+1)})^{(q_1-1)*k_1}=(a-bI)^{(q_1^2-1)*k_1+1}\pmod {q_1}$
$(a-bI)((a-bI)^{(q_2+1)})^{(q_2-1)*k_2}=(a-bI)^{(q_2^2-1)*k_2+1}\pmod {q_2}$
$(a-bI)((a-bI)^{(q_3+1)})^{(q_3-1)*k_3}=(a-bI)^{(q_3^2-1)*k_3+1}\pmod {q_3}$
so we have
$q_2q_3=(q_1^2-1)*k_1+1$ (1)
$q_1q_3=(q_2^2-1)*k_2+1$ (2)
$q_1q_2=(q_3^2-1)*k_3+1$ (3)
(1)/(2)
$\frac{q_2}{q_1}=\frac{(q_1^2-1)*k_1+1}{(q_2^2-1)*k_2+1}$
introduce variable $t$ and it must be a integer.
$(q_1^2-1)k_1+1=q_2t$ (4)
$(q_2^2-1)k_2+1=q_1t$ (5)
tanspose
$(q_1^2-1)k_1=q_2t-1$ (6)
$(q_2^2-1)k_2=q_1t-1$ (7)
(6)*(7)
$q_1q_2t^2-(q_1+q_2)t+1-(q_1^2-1)(q_2^2-1)k_1k_2=0$
$\Delta=(q_1+q_2)^2-4q_1q_2(1-(q_1^2-1)(q_2^2-1)k_1k_2)$
$=(q_1-q_2)^2+4q_1q_2(q_1^2-1)(q_2^2-1)k_1k_2$
$t=\frac{(q_1+q_2)\pm\sqrt{(q_1-q_2)^2+4q_1q_2(q_1^2-1)(q_2^2-1)k_1k_2}}{2q_1q_2}$
$(q_1+q_2)\pm\sqrt{\Delta}=(q_1+q_2)\pm(q_1-q_2)\ne 0\pmod {q_1q_2}$
so $t$ does not exist. therefore the Compsite Number for $N=4k+3$ dose not exist.