Conditions for Quadratic Diophantine Equation to Have Solutions
\[x^2-ny^2= \pm 1\]
does not always have solutions. If \[n \equiv 3 \; (mod \; 4)\]
then working modulus 4 and using the fact that the only quadratic residue modulus 4 is 1 - so that \[x^1 \equiv 1 \; (mod \; 4)\]
for every integer \[x\]
we have \[x^2 -ny^2 \equiv 1-3 \times 1 \; (mod \; 4) =-2 \; (mod \; 4)\]
so no solutions exist. If solutions exist for the equation
\[x^2-ny^2=m\]
then working modulus \[d\]
where \[d\]
is any divisor of \[n\]
we have \[x^2 \equiv m \; (mod \; d)\]
so \[m\]
must be a quadratic residue of \[d\]
.The converse is not true - that is if
\[m\]
is a quadratic residue of \[d\]
that solutions exist.Consider the equation
\[x^2-34y^2=-1\]
. Working modulus 17 \[x^2 \equiv -1 \; (mod \; 17) \equiv 16 \; (mod \; 17)\]
and 16 is a quadratic residue of 17 but the equation has no solutions because the continued fraction for \[\sqrt{34}= [ 5 \lt 1,4,1, 10 gt ]\]
contains a cycle of even length. 
