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.


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.


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.