Encontrar un número compuesto $n$ satisface $(2+3I)^n≡2-3I\pmod{n}$

Question

Como sabemos si $p$ es un número primo impar, a continuación, $$(a+bI)^p\equiv a+(-1)^\frac{p-1}2bI\pmod{p},$$ donde $I=\sqrt{-1}$. Sin embargo, hay cualquier número compuesto $n$ que satisface $$(2+3I)^n≡2-3I\pmod{n}\quad ?$$ Sé $n$ es una solución para la ecuación de $13^{n-1}\equiv 1\pmod{n}$, pero no puede seguir así.

Muchas gracias de antemano.

Answer 1

$${\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. Este rápidamente se entera de que muchas de las soluciones: 1105, 2465, 10585, 29341, 41041, 46657, 115921, 162401, $\ldots$, lo cual está de acuerdo con la lista dada por Zev Chonoles en los comentarios.

Answer 2

He logrado con nada concluyente, pero aquí están algunas de las notas que se espera que puedan ser fuente de inspiración.

1. Dudo que esto es conocido como verdadero, ya que si se cumple, se da una rápida definitiva primalidad de verificación de números de la forma $4k+3$. Entonces, por ejemplo, el probable primer registros no se han de incluir cualquiera de estos números en la lista, por lo que "nadie sabe cómo demostrar o refutar ... primalidad." (Ya he comprobado dos de ellos.)

2. Si $p\equiv 1 \pmod{4}$$(2+3i)^{p-1}\equiv 1 \pmod {p}$. Si hay alguna $k<p-1$ tal que $(2+3i)^k\equiv2-3i\pmod{p}$ $$(2+3i)^{k+1}\equiv 13\pmod{p}$$ y teniendo en cuenta las normas $$13^k\equiv 13 \pmod{p} \\ (2+3i)^{(k+1)(k-1)}\equiv 1 \pmod{p}$$ Me gustaría general de la regla de este caso, pero no puedo, ya que mantiene para $k=19,p=61$.

Si no $k$, $p$ no se puede dividir $n$, por lo que parece prudente concentrarse en sólo números divisibles por los números primos que son 3 modulo 4.

3. Si $p\equiv 3\pmod{4}$ $(2+3i)^{p^2-1}\equiv 1 \pmod{p}$ y podemos encontrar una solución si $n\equiv p \pmod{p^2-1}$. En particular, no será una solución con $n=p^3$ si $13^{p-1}\equiv 1 \pmod{p^3}$. Yo no era capaz de encontrar cualquier prime, pero sospecho que no puede ser descartado por ejemplo, con Hensel del lexema, ya que hay soluciones a $13^{p-1}\equiv 1 \pmod{p^2}$ (por ejemplo,$p=863$).

4. Generalizar a partir de 3, sería suficiente para encontrar $n$ un producto de números primos que son 3 mod 4 tales que para cada uno de los prime $p$ dividiendo $n$ $$\frac{n}{p} \equiv 1 \pmod{p^2-1}$$ Si $n$ es un producto de distintos números primos, entonces todos se deben satisfacer $p^3<n$ y por lo tanto no debe ser de al menos 4.