Let $p$ be a prime, and let $D$ be a quadratic residue modulo $p$. Show that for some $1\leq k\leq |D|$, there exists an integer pair $(x,y)$ that solve $x^2-Dy^2 = kp$
I have managed to prove this for $D < 0$: Since $\left(\frac{D}{p}\right) = 1$, there exists $x$ such that $x^2\equiv D\mod{p}$. Look at all the numbers of the form $t + xs$, $0\leq t,s < \sqrt{p}$. There are $(\lfloor{\sqrt{p}}\rfloor+1)^2$ such pairings, and since $(\lfloor{\sqrt{p}}\rfloor+1)^2 > p$, we get that there exists $s,t,t',s'$ such that $t + xs \equiv t' + xs' \mod{p}$ (the pigeonhole principle). Let $a = t-t', b = s'-s$. Then $a \equiv xb\mod{p}$.
Now, since, $t,t'<\sqrt{p}$, then $|t-t'|<\sqrt{p}$, and therefore $a^2 < p$, and the same holds for $b$. From this, we conclude that $a^2 -Db^2 < (1-D)p = (1+|D|)p$. Also, since $D < 0$, we get that $a^2 - Db^2 > 0$. Also, we notice that $$ a^2 -Db^2 \equiv x^2b^2 - Db^2 = b^2(x^2 - D) \equiv 0\mod{p} $$ To sum up, we get that $0 < a^2-Db^2 < (1+|D|)p$, and also $p$ is a divisor of $a^2-Db^2$, and therefore for some $1\leq k\leq |D|$, $a^2-Db^2 =kp$, as needed.
I am having trouble to use the same method when $D > 0$. The problem occurs when I state that $a^2 - Db^2 > 0$, where it is not necessarily true for $D>0$. Or is it? Can I use the same method for $D > 0$?
The discriminant of $x^2 - D y^2$ is $\Delta = 4 D.$ With $D > 0$ this is positive. I'm assuming $D$ is not a square. With $p$ an odd prime that does not divide $D,$ and $(4D|p) = 1,$ there is some primitive quadratic form that represents $p,$ of the same discriminant. That is, $a x^2 + b xy + c y^2,$ with $\Delta = b^2 - 4 a c.$
We are permitted to demand the form reduced in the sense of Lagrange and Gauss. this is equivalent to $$ ac <0 , \; \; \; b > |a+c|. $$ Since $4D = b^2 - 4 a c > 4|ac|,$ we get $$ |ac| < D. $$ With both $|a|, |c| \geq 1$ we get $|a|, |c| \leq D.$ One of $a,c$ is positive, take $k$ equal to that one. By Gauss composition of the form with its opposite, the principal form represents $kp.$