Are Quadratic Residues the way to the solutions of Quadratic Diophantine Equations

diophantine equationselementary-number-theoryquadratic-residues

Recently i was researching about QRs and i started to think about how we can utilize them. First i asked myself what are the QRs and NRs under the hood. I came up with the following definition: A congruence class A is QR for modulus P IFF

$$xP + A = y^2$$

for some integers $x, y$. So if we rearrange the equation above we can obtain the following form,

$$y^2 -Px = A.$$

which is indeed a Quadratic Diophantine Equation. Are Quadratic Residues the way to the solutions of Quadratic Diophantine Equations? Or for showing them indeed they have solutions?

Best Answer

$y^2-Px=A$ has a solution if and only if $A$ is a quadratic residue modulo $P$, so quadratic residues do provide a way to tell whether or not this kind of quadratic diophantine equation has a solution. But if the equation does have solutions, it doesn't get you very far on the way to finding one.

Related Question