Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

As we know if $p$ is an odd prime number then $$(a+bI)^p\equiv a+(-1)^\frac{p-1}2bI\pmod{p},$$ where $I=\sqrt{-1}$. However, is there any composite number $n$ that satisfies $$(2+3I)^n≡2-3I\pmod{n}\quad ?$$ I know $n$ is a solution to the equation $13^{n-1}\equiv 1\pmod{n}$, but cannot go on.

Many thanks in advance.

share|improve this question
4  
A quick run with Mathematica tells me that there are no such $n$ less than $1,000,000$. It did find a few composite solutions to $$(2+3I)^n\equiv 2+3I\pmod{n},$$ however: $$1105,\; 2465,\; 10585, \;29341,\; 41041,\; 46657$$ –  Zev Chonoles Mar 31 '13 at 7:45
3  
@Zev Chonoles:I know some solutions to the equation $(a+bI)^n≡a-bI\pmod{n}$,for example: $(159+79I)^{399}≡159-79I\pmod{399}$,where $399=3*7*19$. –  Next Mar 31 '13 at 8:11
    
This problem is clearly very similar to the question of Fermat pseudoprimes. I wonder if it might fall into the larger class of Frobenius pseudoprimes; see this excellent paper by Jon Grantham. –  Douglas B. Staple Apr 15 '13 at 3:10
    
The fact that this test has no pseudoprimes $n\leq 10^{10}$ is not completely surprising if any such $n$ has to be a base-13 Fermat pseudoprime as a prerequisite. (Is this indeed the case? I haven't checked it myself; I've only just looked at the argument in Zander's post.) Other tests that combine Fermat tests with other conditions also have not turned up and pseudoprimes see e.g. the Baillie-PSW probable prime test. –  Douglas B. Staple Apr 15 '13 at 3:16

2 Answers 2

up vote 8 down vote accepted
+100

$${\Large \textrm{There is no such }n\leq10^{10}}$$

When doing a brute-force numerical search on this problem, there are two obvious modes of attack.

One method is to compute $(2+3I)^n\ \forall\ n\leq N$ iteratively via $(2+3I)^n = (2+3I)(2+3I)^{n-1}$, and only reduce $\operatorname{mod} n$ to check the congruence for each $n$. $(2+3I)^n$ has $O(n)$ digits, so each multiply takes $O(n)$ time. Doing $N$ such multiplies brings the overall complexity to $O(N^2)$.

A more efficient algorithm is to compute $(2+3I)^n\ (\operatorname{mod}\ n)$ separately for each $n$ using e.g. a binary ladder, reducing $\operatorname{mod} n$ at each stage of the binary ladder. Checking a single $n$ takes $\log(n)$ this with approach, resulting in a total time complexity of $O(N\log N)$ to check all $n\leq N$.

The complexity arguments given above are only estimates. However, I implemented both algorithms and found that they are borne out in practice: the two algorithms both take ~3s to check all $n\leq 10^5$ using one core on my system. From that point on, the first algorithm takes roughly quadratic time, whereas the second one takes roughly linear time.

Here is my implementation in PARI/GP of the faster of the two algorithms:

\\ Our search range
NMIN=2;
NMAX=100000000;


\\ Computes x^y (mod n) using a binary ladder
\\ This is Algorithm 9.3.1 from Crandall and Pomerance, "Prime Numbers", 2 Ed.
\\ RETURNS x (RATHER THAN 1) IF y=0...
pow_modN(x,y,n)={
  \\ Get: 1) y_binary (the binary expansion of y)
  \\      2) D        (the number of bits in y_binary)
  \\         Unfortunately these are not interleaved!
  y_binary = binary(y);
  y_shl_D=y;
  D=0;
  while(y_shl_D,
    D++;
    y_shl_D>>=1;
  );

  \\ Initialize to z=x.
  \\ Loop over bits of y, starting with the next-to-highest
  \\ y_binary[1] is the MSB, y_binary[D] is LSB.
  z=x;
  for(j=2, D,
    z*=z;
    if(y_binary[j], z*=x);
    z%=n;
  );

  \\ Return z=x^y (mod n)
  z;
}


\\ We work in the field of Gaussian integers, Z(w) here w==I==sqrt(-1).
w=quadgen(-4);

\\ We intend to exponentiate a.
a = 2+3*w;

\\ Compute a^n for all n in [NMIN,NMAX]
for(n=NMIN, NMAX, {
  zPowN_modN = pow_modN(a, n, n);
  re_zPowN_modN = real(zPowN_modN);
  im_zPowN_modN = imag(zPowN_modN);

  if(re_zPowN_modN-2,,
    if(im_zPowN_modN-n+3,,
      if(isprime(n),,
        print(n);
      );
    );
  );

  if(n%100000,,printf("Done to %u\n", n));

});

quit;

Negative results with numerical searches like this one are dangerous, because many different errors would produce the same result. For example, in C, (-1)%4 == 3%4 evaluates to -1==3 which is false, despite the fact that $-1\equiv3\ (\operatorname{mod}\ 4)$. To get the desired result, one has to check (-1-3)%4==0, which returns true. Considering this, double checks are necessary.

For the above code I checked the result in two ways. Firstly, I dropped the requirement that $n$ be composite, which results in a long list of primes $n=3, 7, 11, 19, 23, \ldots$ I redid this calculation with a different algorithm (the "first algorithm above"), different software (Maple) and different hardware (my laptop), and compared the resulting lists up to $10^6$, with no differences found.

My second double check was to make a minor modification to the above code to check the congruence $(2+3I)^n \equiv 2+3I\ (\operatorname{mod}\ n)$ for composite $n$. This quickly finds many solutions: 1105, 2465, 10585, 29341, 41041, 46657, 115921, 162401, $\ldots$, which agrees with the list given by Zev Chonoles in the comments.

share|improve this answer
    
@Sophie PS. Considering your comment that $n$ has to be a base-$13$ Fermat pseudoprime, I also checked all Carmichael numbers up to $10^{18}$, and all 3-prime Carmichael numbers up to $10^{24}$, with no luck. If someone has a list of base-$13$ Fermat pseudoprimes, then I'd be happy to check it as well. –  Douglas B. Staple Apr 14 '13 at 2:32
    
,Thanks for your efforts to this problem,I will add more ideas from myself if I have time,but I'm so busy right now. –  Next Apr 14 '13 at 4:48

I have managed to come up with anything conclusive, but here are some notes that hopefully can be inspiring.

1. I doubt this is well known as true, since if true it gives a fast definitive primality check for numbers of the form $4k+3$. Then for example the probable prime records wouldn't have to include any such numbers in the list for which "nobody knows how to prove or disprove ... primality." (I have already checked two of them.)

2. If $p\equiv 1 \pmod{4}$ then $(2+3i)^{p-1}\equiv 1 \pmod {p}$. If there is any $k<p-1$ such that $(2+3i)^k\equiv2-3i\pmod{p}$ then $$ (2+3i)^{k+1}\equiv 13\pmod{p} $$ and by considering the norms $$ 13^k\equiv 13 \pmod{p} \\ (2+3i)^{(k+1)(k-1)}\equiv 1 \pmod{p} $$ I'd like to generally rule this case out, but I cannot, since it holds for $k=19,p=61$.

If there's no such $k$, then $p$ cannot divide $n$, so it seems prudent to concentrate on numbers only divisible by primes that are 3 modulo 4.

3. If $p\equiv 3\pmod{4}$ then $(2+3i)^{p^2-1}\equiv 1 \pmod{p}$ and we might find a solution if $n\equiv p \pmod{p^2-1}$. In particular there will be a solution with $n=p^3$ if $13^{p-1}\equiv 1 \pmod{p^3}$. I wasn't able to find any such prime, but suspect it can't easily be ruled out e.g. with Hensel's lemma, since there are solutions to $13^{p-1}\equiv 1 \pmod{p^2}$ (e.g. $p=863$).

4. Generalizing from 3, it would be sufficient to find $n$ a product of primes that are 3 mod 4 such that for each prime $p$ dividing $n$ $$ \frac{n}{p} \equiv 1 \pmod{p^2-1} $$ If $n$ is a product of distinct primes then they all must satisfy $p^3<n$ and hence there must be at least 4.

share|improve this answer
1  
:Thanks for your bounty from your own reputation at first,it makes more people to care about this question since someone think this is an interest problem.I also tried to solve this problem with factories method,but failed.BTW,If I don't accept any answer before tommorow,where will the reputation gone?Will it lost or return to your account?If it will lost,I prefer to accept your answer to avoid it. –  Next Apr 14 '13 at 18:03
    
"I doubt this is well known as true, since if true it gives a fast definitive primality check for numbers of the form 4k+3." Exactly. If there are no pseudoprimes to this test, then it would give a very fast polynomial time primality proof for such numbers; this would be an important result in computational number theory. –  Douglas B. Staple Apr 15 '13 at 3:00

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.