Show $a^2 + b^2 + 1 \equiv 0 \mod p$ always has a solution if $p = 4k+3$

Question

If $p = 4k+3$ is a prime number (so $p = 7,11,19$ but not $p = 5,13$ or $p =15$) then there are numbers $a,b$ such that:

$$a^2 + b^2 + 1 \equiv 0 \mod p$$

For example $2^2 + 3^2 + 1 = 14 = 7 \times 2\equiv 0 \mod 7 $.

My reasoning was that in the finite field $\mathbb{F}_{p^2}$, $-1$ is always a perfect square

• if $p = 4k+1$ then $-1$ is a perfect square in $\mathbb{F}_p$
• if $p = 4k+3$ then $x^2 +1 $ is irreducible then always $\mathbb{F}_p[x]/(x^2+1) \simeq \mathbb{F}_{p^2}$

I remember this as $i = \sqrt{-1} \in \mathbb{F}_p$ if $p = 4k+1$ and $i = \sqrt{-1} \in \mathbb{F}_p^2$ if $p = 4k+3$

Then somehow I made the magical conclusion that we always had a solution for $z \overline{z} = -1$ with $z = a+bx$

$$z \overline{z} = (a+bx)(a-bx) = a^2 + b^2 = -1 $$

This does not logically follow, but I made a leap of intution. What is the correct logic here?

This is a variant of Fermat's theorem that $p = 4k+1$ can be written as the sum of two squares: $p = a^2 + b^2$ but that is not a congruence. That is an equality involving whole numbers $a,b \in \mathbb{Z}$.

Answer 1

I'm not sure how to modify/fix your construction, but for reference the "standard" argument is that since $p$ is prime, $-a^2$ and $b^2+1$ both run over $(p+1)/2$ distinct values for $a,b\in \mathbb{F}_p$, and so must agree on at least one value.

Notice that this works for any (odd) prime, not just those of the form $4k+3$, but that in the case $p\equiv 1 \bmod 4$ you can additionally take $a=0$.

Answer 2

The argument given by user7530 is what I would recommend as well. It gets everything done inside $\Bbb{F}_p$.

Your intuitive leap can also be justified. The mapping $z\mapsto z\overline{z}$ is known as the relative norm map. We can view it differently. The Galois theory of extensions of finite fields tells us that the non-trivial $\Bbb{F}_p$-automorphism of $\Bbb{F}_{p^2}$ is the Frobenius mapping $z\mapsto z^p$. So we know $N(z)=z\overline{z}=z^{p+1}$ for all $z\in\Bbb{F}_{p^2}$.

The key to success is to recall the fact that the multiplicative groups $\Bbb{F}_{p^2}^*$ and $\Bbb{F}_{p}^*$ are cyclic of respective orders $p^2-1$ and $p-1$. The basic facts about cyclic groups tell us that raising to power $p+1$ is a surjective homomorphism between the two groups. Therefore any element of $\Bbb{F}_p$ is the norm of some element of $\Bbb{F}_p$ - the element $-1$ in particular.

The assumption $p\equiv3\pmod4$ is used as it gives us the description $\Bbb{F}_{p^2}=\Bbb{F}_p[i]$, where $i^2=-1$. User7530's argument is immune to that detail.