Solving a Diophantine Equation

Question

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?

Answer 1

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.$

Answer 2

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.