Dado un número entero $N$ encontrar soluciones a $X^3 + Y^3 + Z^3 - 3XYZ \equiv 1 \pmod{N}$

Question

Dado un número entero $N > 0$ con factorización desconocida, me gustaría encontrar soluciones no triviales $(X, Y, Z)$ a la congruencia $X^3 + Y^3 + Z^3 - 3XYZ \equiv 1 \pmod{N}$ . ¿Existe alguna forma algorítmica de encontrar rápidamente estas tuplas? Un caso especial surge al tomar $Z \equiv 0 \pmod{N}$ en cuyo caso podemos considerar la congruencia más simple $X^3 + Y^3 \equiv 1 \pmod{N}$ . ¿Alguien sabe cómo se puede encontrar este tipo de $(X, Y)$ ?

Answer 1

Por el Teorema del Resto Chino, podemos reducir a los siguientes casos:

1. $N$ es coprima con $6$
2. $N$ es una potencia de $3$
3. $N$ es una potencia de $2$

Supongamos que $N$ es coprima con $6$ y que $-3$ es un cuadrado mod $N$ , digamos que $\rho^2=-3\pmod{N}$ . Poner $\omega=(-1+\rho)/2$ así que $\omega^2=\omega^{-1}=-1-\omega=(-1-\rho)/2$ en $\mathbb{Z}/N$ . Poner \begin{align*} X &= (U+V+W)/3 \\ Y &= (U+\omega V+\omega^2W)/3 \\ Z &= (U+\omega^2V+\omega W)/3 \end{align*} Entonces su ecuación se convierte en $UVW=1\pmod{N}$ para que pueda tomar $U$ y $V$ para ser números arbitrarios que son coprimos a $N$ y $W=1/(UV)\pmod{N}$ .

No he averiguado qué pasa si $N$ es coprima con $6$ pero $-3$ no es un mod cuadrado $N$ .

Para los otros dos casos, el experimento sugiere lo siguiente. Supongamos que $N=p^m$ con $p\in\{2,3\}$ y $m\geq 2$ . Supongamos que $X,Y\in\mathbb{Z}/N$ se dan, con $X=Y=0\pmod{p}$ . Si $p=2$ entonces hay un único $Z\in\mathbb{Z}/N$ con $f(X,Y,Z)=1$ . Si $p=3$ En cambio, hay $3$ opciones para $Z$ . En cualquier caso, siempre tenemos $Z=1\pmod{p}$ . También podemos permutar estas soluciones cíclicamente, lo que da otro factor de $3$ . Si $p=2$ esto da $3.2^{2m-2}$ soluciones en total, y si $p=3$ entonces el número es $3^{2m}$ . Todo esto debería ser demostrable mediante una especie de iteración Newton-Raphson, pero no he resuelto los detalles.

Answer 2

Curiosamente, la solución es finita.

para la ecuación:

$$X^3+Y^3+Z^3-3XYZ=q=ab$$

Si es posible descomponer el coeficiente de la siguiente manera: $4b=k^2+3t^2$

Entonces las soluciones son de la forma

$$X=\frac{1}{6}(2a-3t\pm{k})$$

$$Y=\frac{1}{6}(2a+3t\pm{k})$$

$$Z=\frac{1}{3}(a\mp{k})$$

Pensé que la solución está determinada por la ecuación Pell, pero al calcular el signo fue un error. No hay diferencia, pero la cantidad debe ser. Por lo tanto, el número de soluciones por supuesto.

Sin embargo, puedo estar equivocado. Todavía tenemos que comprobar otras opciones.