Solving a Diophantine Equation Let $p \equiv q \equiv 3 \pmod 4$ for distinct odd primes $p$ and $q$. Show that $x^2 - qy^2 = p$ has no integer solutions $x,y$.
My solution is as follows.
Firstly we know that as $p \equiv q \pmod 4$ then $\big(\frac{p}{q}\big) = -\big(\frac{q}{p}\big)$
Assume that a solution $(x,y)$ does exist and reduce the original equation modulo $q$ to get $x^2 \equiv p \pmod q.$ This implies $\big(\frac{p}{q} \big) =  1 $. 
Now if we reduce the original equation modulo $p$ then $x^2 \equiv qy^2 \pmod p \ (*)$. To get a contradiction I want to show that $\big(\frac{q}{p}\big) =1$ and to do this I need to prove that $gcd(p.y) = 1$ as this means we can divide both sides of ($*$) by $y^2$. But how do you prove this?
 A: You started out well enough. You got to: the assumption of a solution implies $(p|q) = 1$ and so $(q|p ) = -1.$
Next, we think we have $x^2 - q y^2  = p,$ in particular 
$$ x^2 \equiv q y^2 \pmod p.  $$ If $y \neq 0 \pmod p,$ then $y$ has a multiplicative inverse $\pmod p,$ and
$$ \left( \frac{x}{y} \right)^2 \equiv q \pmod p.   $$ Well this contradicts  $(q|p ) = -1,$ so in fact $y$ is divisible by $p.$ But then $x^2 - q y^2  = p$ says that $x$ is also divisible by $p.$ Thus $$ x^2 - q y^2 \equiv 0 \pmod {p^2},  $$ which contradicts  $x^2 - q y^2  = p.$
An answer was posted using just $\pmod 4,$ which is worth knowing.
However, the part about a value of the Legendre symbol implying that $x,y$ are both divisible by some prime is a standard ingredient in  quadratic forms and will come up again and again. 
The full version is this: if I have a quadratic form $$ f(x,y) = a x^2 + b x y + c y^2,  $$ it has a "discriminant" that is the same as the term under the square root in the Quadratic Formula,
$$  \Delta = b^2 - 4 a c.  $$
Now, $\Delta$ is allowed to be positive or negative, however if it is positive we do not permit it to be a perfect square. The technical term for binary quadratic forms with square discriminant is "stupid." 
Now, suppose we have some prime $p$ that does not divide  $\Delta,$ and for which
$$   (\Delta | p)  = -1.  $$ Note that we allow $p \equiv \pm 1 \pmod 4$ here.
What happens if
$$ a x^2 + b x y + c y^2 \equiv 0 \pmod p?        $$ 
Just to make it easy on myself, demand that $a$ not be divisible by $p.$
If so, it is still true if I multiply both sides by $4a,$ I get
$$ 4 a^2 x^2 + 4 a b x y + 4 ac y^2 \equiv 0 \pmod p,        $$ and
$$ 4 a^2 x^2 + 4 a b x y + b^2 y^2 - b^2 y^2 + 4 ac y^2 \equiv 0 \pmod p,        $$
$$ (2 a x + b y)^2 - \Delta y^2  \equiv 0 \pmod p,        $$ so
$$ (2 a x + b y)^2 \equiv \Delta y^2    \pmod p.        $$
If we assume that $y$ is not divisible by $p,$ it has a multiplicative inverse $\pmod p,$ and we get a square equivalent to $\Delta \pmod p,$ not permitted. So actually $y$ is divisible by $p.$ Next $(2ax+ by)$is divisible by $p,$ and finally $x$ is as well as $y$ because I demanded that $a$ n not be. So there.
The bit about $a$ not being divisible by $p$ is not critical. As $\Delta$ is not divisible by $p$ it is impossible for $a,b,c$ to all be divisible by $p.$ And hilarity ensues. It has come back to me, as in a dream. If $a$ is divisible by $p,$ simply switch the argument to $c,$ multiply by $4c$ rather than $4a$ and so on. We might worry about both $a,c$ being divisible by $p,$ but in that case 
$\Delta \equiv b^2 \pmod p $ and $(\Delta | p) = (b^2 | p) =1, $ contradicting $(\Delta | p) = -1.$
A: You probably tried too hard on this. We know $x^{2},y^{2}\equiv 1/0\pmod{4}$. So $x^{2}$ choices are $0,1$. We have $0-1=3$, $1-2=3$. $qy^{2}$ cannot be $1\pmod{4}$. Thus $x$ must be odd and $y$ be even. But if that is so $qy^{2}$ must be $0\pmod{4}$, which contradicts with our assumption $qy^{2}\equiv 2\pmod{4}$. This showed the original equation has no solution. 
