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?


2 Answers 2


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

  • $\begingroup$ Thank you very much for a such a detailed and informative answer! $\endgroup$
    – Anon
    Apr 22, 2012 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.