Solutions to nonhomogeneous quadratic equation mod $N$ Is there any way to find non-trivial solutions to the equation $x^2 + y^2 - x \equiv 0 \mod{N}$? There are clearly several trivial solutions, for example $(x, y) = (0, 0), (1, 0), (2^{-1}, 2^{-1}), (2^{-1}, -2^{-1})$. By trivial solution, I mean one that holds for all choices of $N$ and hence do not tell us anything about the structure of any specific $N$. In this problem, assume the factorization of $N$ is not known.
 A: In order to get solutions of the congruence you are interested in let us consider the equation $x^2+y^2-x-Nz=0$. Using the trivial solution $x=1, y=0, z=0$, we parametrize all rational solutions by taking $x=t+1, y=ut, z=vt$, where $t, u, v$ are rational parameters. Note that for $t=0$ we get our trivial solutions $(x,y,z)=(1,0,0)$. Solving the resulting quadratic equation for $t$, we see that $t = \frac{Nv-1}{u^2 + 1}$, hence
$$
x=\frac{Nv+u^2}{u^2+1},\quad y=\frac{u (Nv-1)}{u^2+1},\quad z=\frac{v (Nv-1)}{u^2+1}.
$$
Since we are interested in integral solutions of the congruence, it is enough to choose integers $u$ in such a way that $u^2+1$ is coprime to $N$. If this condition is satisfied, then we compute $(u^2+1)^{-1}\pmod{N}$ and get the solutions. Note that, to do this we don't need to have a factorization of $N$.
For example, if you take $N=1234567$ it is enough to take $u=2$ and say $v=1$. Then $(u^2+1)^{-1}\pmod{N}$ is equal to $493827$, and the solution (after reduction $\pmod{N}$) is
$$
x=740741, \quad y=246913.
$$
