# 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?

-

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

-
Thank you very much for a such a detailed and informative answer! –  Alex Kite Apr 22 '12 at 2:18
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.