Let $p > 2$ be prime. Show that there exist integers $a,b \geq 0 $ satisfying the congruence $a^2 + b^2 \equiv -1 $(mod $p$).

Question

Let $p > 2$ be prime. Show that there exist integers $a,b \geq 0 $ satisfying the congruence $a^2 + b^2 \equiv -1 $(mod $p$).

A few things that can be seen instantly: $ p \equiv 1$ mod $4$, and I am contemplating using Wilsons theorem: $(p-1)! \equiv -1$ mod $p$.

Alternatively there is the consideration of sets $\{1+a^2 : 0 \leq a \leq \frac{p-1}{2} \}$ and $\{-b^2 : 0 \leq b \leq \frac{p-1}{2} \}$,

Is it true that $1+ a^2 = -b^2$ and hence $a^2 + b^2 \equiv -1$ mod $p$ ? I'm sure this isn't completely correct, nor is it rigorous enough - can anyone tell me the answer?

I don't understand "$p\equiv 1$ mod $4$". – TonyK May 31 '15 at 13:24 — TonyK, May 31 '15 at 13:24

score 1 · Accepted Answer · answered May 31 '15 at 13:21

Consider those two sets. These are two subsets of $\mathbf{Z}/p\mathbf{Z}$ of order $\frac{p+1}{2}$ each. Since $\mathbf{Z}/p\mathbf{Z}$ has p elements, and the sum of the cardinalities o the two sets is $p+1>p$, then these two sets must intersect. Could you continue?

Let $p > 2$ be prime. Show that there exist integers $a,b \geq 0 $ satisfying the congruence $a^2 + b^2 \equiv -1 $(mod $p$).

1 Answers1