TITLE: If $p$ is a prime and $p\equiv1\pmod 4$, then $x^2+4=py^2$ has solutions
QUESTION [3 upvotes]: Prove that if $p$ is a prime and $p\equiv1\pmod 4$, then $x^2+4=py^2$ has integer solutions.

This is related to units in quadratic number field $\mathbb Q(\sqrt p)$. As far as I know, $x^2+4\equiv0\pmod p$ has a solution because $-4$ is a quadratic residue modulo $p$. However, it is not sufficient to prove that. Any help will be appreciated.

REPLY [4 votes]: As Jyrki comments, one needs to prove that $u^2-pv^2=-1$ is soluble in integers.
This is a well-known corollary of the theory of Pell's equation.
There is a minimal solution of Pell's equation
$$a^2-pb^2=1$$
in positive integers with $a$ (or $b$) as small as possible.
Note that $b$ must be even, as if $b$ is odd $pb^2+ 1 \equiv2\pmod 4$
and so cannot be a square. Therefore $a$ is odd. Then
$$pb^2=a^2-1=(a-1)(a+1)$$
and so
$$p\left(\frac{b}2\right)^2=\left(\frac{a-1}2\right)\left(\frac{a+1}2\right)$$
and as $(a-1)/2$ and $(a+1)/2$ are coprime positive integers, one is a square
and the other $p$ times a square.
In any case,
$$1=\frac{a+1}2-\frac{a-1}2$$
and so $1$ equals either $u^2-pv^2$ or $pv^2 - u^2$ for some positive integers $u$
and $v$. The former would contradict the minimality of $(a,b)$ as a solution
to Pell's equation; the latter is what we want.
{"set_name": "stack_exchange", "score": 3, "question_id": 3716321}