1
$\begingroup$

I wonder if solutions are known for this quadratic diophantine modular equation: x²=y² mod (p1 p2) where p1,p2 are given primes and x,y are integers and unknowns?

$\endgroup$
1
$\begingroup$

We assume that the $p_i$ are distinct, and deal with the case the $p_i$ are odd. The argument for the case one of the primes, say $p_1$, is $2$ is essentially the same.

We are told that $p_1p_2$ divides $(x-y)(x+y)$. Perhaps (i) $p_1p_2$ divides $x-y$. That gives the solution $x\equiv y\pmod{p_1p_2}$. Or perhaps (ii) $p_1p_2$ divides $x+y$. That gives the solution $x\equiv -y\pmod{p_1p_2}$.

Or perhaps (iii) $p_1$ divides $x-y$ and $p_2$ divides $x+y$, or perhaps (iv) $p_1$ divides $x+y$ and $p_2$ divides $x-y$.

For case (iii) we have $x\equiv y\pmod{p_1}$ and $x\equiv -y\pmod{p_2}$. So $y=x+tp_1$ for some $t$, and $x+y=2x+tp_1\equiv 0\pmod{p_2}$. Let $x$ be arbitrary in the interval $[0.p_1p_2-1]$, and solve the linear congruence $tp_1\equiv -2x\pmod{p_2}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.