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.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ The number of different solutions may be proportional to $N$. Are you interested in just one? $\endgroup$– Max AlekseyevCommented Sep 23, 2020 at 2:44
-
$\begingroup$ Sure, I'd take any solution. Suppose $N = 1234567$. Can you find any nontrivial $(x, y)$? $\endgroup$– GautamCommented Sep 23, 2020 at 3:59
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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. $$
-
$\begingroup$ I don't quite follow your answer. I verified that your choice $(x, y)$ is indeed a solution to the equation for $N = 1234567$. Can you explain what you mean by "using the trivial solution $x = 1, y = 0, z = 0$? How did you use this solution? Also, if we take $y = ux$, $z = vx$, we obtain the equation $x^2 + u^2x^2 - x - Nvx = 0$, whose solution is $x = \frac{vN + 1}{u^2 + 1}$, which is not the solution you described... I think your answer might have some small typos. I'm really interested to hear what you figured out, though! $\endgroup$– GautamCommented Sep 24, 2020 at 6:36
-
$\begingroup$ @Gautam Of course you are right. I was to quick. I edited the answer and believe that everything is clear now. $\endgroup$ Commented Sep 24, 2020 at 8:45
-
$\begingroup$ Thanks, this is now clear. Does this capture all solutions? Intuitively, the family of solutions should depend on only one parameter, since there are two unknowns ($x$ and $y$) and one constraint. This leads me to believe that your proposal indeed captures all possible solutions, but I'm not sure how to prove it. $\endgroup$– GautamCommented Sep 24, 2020 at 22:36
-
$\begingroup$ @Gautam My parametrization is invertible over $\mathbb{Q}$ but not necessarily modulo $N$. Indeed, the inverse is given by $u=y/(x-1), v=z/(x-1)$ (here $z=(x^2+y^2-x)/N$) and can be computed modulo $N$ provided that $x-1$ is coprime to $N$. $\endgroup$ Commented Sep 26, 2020 at 9:58