## Conditions for Quadratic Diophantine Equation to Have Solutions

The Diophantine equation
$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$
$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.