Given an integer $N$, find solutions to $X^3 + Y^3 + Z^3 - 3XYZ \equiv 1 \pmod{N}$ Given an integer $N > 0$ with unknown factorization, I would like to find nontrivial solutions $(X, Y, Z)$ to the congruence $X^3 + Y^3 + Z^3 - 3XYZ \equiv 1 \pmod{N}$. Is there any algorithmic way to rapidly find such tuples? One special case arises by taking $Z \equiv  0 \pmod{N}$, in which case we can consider the simpler congruence $X^3 + Y^3 \equiv 1 \pmod{N}$. Does anyone know how to find such $(X, Y)$?
 A: Since, $X^3+Y^3+Z^3-3XYZ=\frac{1}{2}(X+Y+Z)((X-Y)^2+(Y-Z)^2+(Z-X)^2)$, taking $X,Y,Z$ close to each other give some non-trivial and cheap solutions.
For instance $(k+1,k,k)$ for $N=3k$, $(k+1,k+1,k)$ for $N=3k+1$, $(k+1,k,k-1)$ for $N=9k-1$, etc.
A: By the Chinese Remainder Theorem, we can reduce to the following cases:

*

*$N$ is coprime with $6$

*$N$ is a power of $3$

*$N$ is a power of $2$
Suppose that $N$ is coprime with $6$ and that $-3$ is a square mod $N$, say $\rho^2=-3\pmod{N}$.  Put $\omega=(-1+\rho)/2$ so $\omega^2=\omega^{-1}=-1-\omega=(-1-\rho)/2$ in $\mathbb{Z}/N$.  Put
\begin{align*}
 X &= (U+V+W)/3 \\
 Y &= (U+\omega V+\omega^2W)/3 \\
 Z &= (U+\omega^2V+\omega W)/3
\end{align*}
Then your equation becomes $UVW=1\pmod{N}$, so you can take $U$ and $V$ to be arbitrary numbers that are coprime to $N$, and $W=1/(UV)\pmod{N}$.
I have not worked out what happens if $N$ is coprime with $6$ but $-3$ is not a square mod $N$.
For the other two cases, experiment suggests the following.  Suppose that $N=p^m$ with $p\in\{2,3\}$ and $m\geq 2$.  Suppose that $X,Y\in\mathbb{Z}/N$ are given, with $X=Y=0\pmod{p}$.  If $p=2$, then there is a unique $Z\in\mathbb{Z}/N$ with $f(X,Y,Z)=1$.  If $p=3$, there are instead $3$ choices for $Z$.  In either case, we always have $Z=1\pmod{p}$.  We can also permute these solutions cyclically, which gives another factor of $3$.  If $p=2$ this gives $3.2^{2m-2}$ solutions in total, and if $p=3$ then the number is $3^{2m}$.  All this should be provable by a kind of Newton-Raphson iteration, but I have not worked out the details.
A: Here is a method to find your triples that is not rapid, perhaps trivial, and highly conjectural.  Hopefully it is still of some interest.  First, find positive integers $x$, $y$, and $z$ that solve $x^3+Ny^3+N^2z^3-3Nxyz=1$.  This step is not difficult but may take some time.  See: https://math.stackexchange.com/questions/3481203/units-in-cube-root-system/3483357#3483357 for some details.  Next, raise the solution to the $2N$th power.  The result will solve your equation.
For example, if $N=2$ then $(1,1,1)$ is a solution to the cubic pell equation.  Then $(1,1,1)^4=(73,58,46)$ is a solution to $X^3 + Y^3 + Z^3 - 3XYZ \equiv 1 \pmod{N}$.  I have tested this for non-cube $N$ with $1<N<2000$.
A: Strangely enough, the solution is finite.
for the equation:
$$X^3+Y^3+Z^3-3XYZ=q=ab$$
If it is possible to decompose the coefficient as follows:  $4b=k^2+3t^2$
Then the solutions are of the form:
$$X=\frac{1}{6}(2a-3t\pm{k})$$
$$Y=\frac{1}{6}(2a+3t\pm{k})$$
$$Z=\frac{1}{3}(a\mp{k})$$
Thought the solution is determined by the equation Pell, but when calculating the sign was a mistake. There's no difference, but the amount should be. Therefore, the number of solutions of course.
I may be wrong, though. We still need to check other options.
