Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How to prove the Diophantine equation : $x^2 - 71y^2 = -1$ has no solution with $x,y$ in the set of integers?

I am stuck on this question for a long time and i cant really understand how to prove it. Can someone help please?

share|cite|improve this question
A solution to that would in particular have $x^2 \equiv -1 \pmod{71}$. But since $71 \equiv 3 \pmod{4}$, that congruence has no solution. – Daniel Fischer Nov 3 '13 at 1:48
Thank you for your comment! I kind of understand the first part x^2≡−1(mod71). However, i am wondering why do we need to put (mod 4) for the second part? – water723 Nov 3 '13 at 1:55
For primes $p \equiv 1 \pmod 4,$ not only can we always solve $v^2 \equiv -1 \pmod p,$ we can always solve $x^2 - p y^2 = -1.$ Proof in Mordell's book.… – Will Jagy Nov 3 '13 at 2:04
It’s because $-1$ is not a square modulo $71$. – Lubin Nov 3 '13 at 2:04
Good. Now that you understand, you can write it up and post it as an answer. This helps clear the Unanswered Questions list. – Gerry Myerson Nov 3 '13 at 3:07
up vote 1 down vote accepted

A solution to a Pell-type equation

$$x^2 - Dy^2 = a\tag{1}$$

gives in particular a solution to the congruence

$$x^2\equiv a \pmod{D}.\tag{2}$$

So a necessary condition for the solubility of $(1)$ is that $a$ be a quadratic residue modulo $D$, hence modulo every prime dividing $D$.

It is easy to see that $x^2 \equiv -1 \pmod{p}$ has no solution if $p$ is a prime $\equiv 3 \pmod{4}$, since for $p > 2$, the congruence $x^2\equiv -1\pmod{p}$ implies that the multiplicative order of $x$ modulo $p$ is $4$, hence $4 \mid (p-1)$, or $p \equiv 1 \pmod{4}$. Since $71 \equiv 3 \pmod{4}$, there is no solution to $x^2 \equiv -1 \pmod{71}$, and a fortiori no solution to $x^2 - 71 y^2 = -1$.

Thus a necessary condition for the existence of solutions to

$$x^2 - Dy^2 = -1$$

is that $D$ has no prime divisors $\equiv 3\pmod{4}$, and that $D$ is not divisible by $4$, and not a perfect square (if $D > 1$). But these conditions are not sufficient, for example $x^2-34y^2 = -1$ and $x^2 - 221y^2 = -1$ have no solutions although $34 = 2\cdot 17$ and $221 = 13\cdot 17$ satisfy these conditions.

It is less easy to see, but true, that for every prime $p \equiv 1 \pmod{4}$ the equation $x^2 - p y^2 = -1$ has solutions.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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