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

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?

-
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. books.google.com/books/about/… – 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

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.

-