Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
How do you prove the statement in the first sentence? –  Igor Rivin Dec 2 '12 at 5:45
    
@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. –  Todd Trimble Dec 2 '12 at 12:39
2  
Search for Frobenius pseudoprimes. –  Felipe Voloch Dec 2 '12 at 16:10
    
Possibly helpful reference on Frobenius pseudoprimes : MR1680879 (2001g:11191) Grantham, Jon . Frobenius pseudoprimes. Math. Comp. 70 (2001), no. 234, 873--891 ams.org/journals/mcom/2001-70-234/S0025-5718-00-01197-2/… –  François Brunault Dec 3 '12 at 9:14
add comment

3 Answers

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.

share|improve this answer
    
Hm, is it possible that your condition implies the number is Carmichael? –  joro Dec 3 '12 at 6:24
    
I thought it did imply that. For any $\alpha \in \mathbb{Z}$, we have $\alpha^N \equiv \bar{\alpha} = \alpha \; \pmod N$. –  Todd Trimble Dec 3 '12 at 12:11
    
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. –  joro Dec 3 '12 at 15:39
add comment

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.

share|improve this answer
    
we can still deal with for five factors. so there isn't any composite number sastifies the conditions. –  wanglei Dec 3 '12 at 9:48
    
if q=4k+1 and prime, then (a+bi)^q is (a+bi) and NOT (a-bi). the "-" is only for prime q=4k+3. your proof is wrong from the start, please recheck it. –  user29817 Dec 20 '12 at 7:10
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.