Question: if $d$ is a positive integer that is divisible by a prime $p \equiv 3 \bmod 4$, then $x^2 - dy^2 = -1$ has no solutions.

My attempts:

Try to show that if $p \equiv 3 \bmod 4$ is a prime then $x^2 \equiv -1 \bmod p$ has no solution. Proof, almost:

$x^2 \equiv -1 \bmod p \to (x^2)^{\frac{p-1}{2}} \equiv x^{p-1} \equiv (-1)^{\frac{p-1}{2}} \bmod p$

  • if $\frac{p-1}{2}$ is even (which in fact is not even) then: $x^{p-1} \equiv 1 \bmod p$

    $\to$ when $p \nmid x$ according to Fermat's little theorem it is True.

    $\to$ when $p \mid x$ then $x^{p-1} \not \equiv 1 \equiv 0 \bmod p$, useless

  • if $\frac{p-1}{2}$ is odd, which in fact $p$ is odd because: $p \equiv 3 \bmod 4$ then: $x^{p-1} \equiv -1 \bmod p$, Question: How to show this has no solution?

Assuming we proved Question is True, then:

$(x^2 - dy^2 = -1) \bmod p \to (x^2 = -1) \bmod p$

Any help will be appreciated.


1 Answer 1


You almost have it. Fermat's Little Theorem says that $x^{p-1}\equiv 1\pmod p$, so it can not be $-1$.

By the way, the proof that $p\equiv 1\pmod 4$ implies that $-1$ is a square mod $p$ is wrong. You have shown that $x\equiv -1\pmod p$ implies a true identity, but this proves nothing. This reasoning is wrong:

A implies B, and B is true. Therefore, A is true.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .