13
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ How do you prove the statement in the first sentence? $\endgroup$
    – Igor Rivin
    Dec 2, 2012 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, 2012 at 12:39
  • 3
    $\begingroup$ Search for Frobenius pseudoprimes. $\endgroup$ Dec 2, 2012 at 16:10
  • 1
    $\begingroup$ 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/… $\endgroup$ Dec 3, 2012 at 9:14

3 Answers 3

6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Hm, is it possible that your condition implies the number is Carmichael? $\endgroup$
    – joro
    Dec 3, 2012 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, 2012 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, 2012 at 15:39
5
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ we can still deal with for five factors. so there isn't any composite number sastifies the conditions. $\endgroup$
    – wanglei
    Dec 3, 2012 at 9:48
  • $\begingroup$ 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. $\endgroup$
    – user29817
    Dec 20, 2012 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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