For every prime p there is a sum of squares congruent to -1 mod p

Question

For every prime $p$, there exists $a,b \in \mathbb{Z}$ such that $p\mid a^2+b^2+1$

For context, this question shows up as a statement on a hint to showing that every positive integer is a sum of 4 squares using the Hurwitz Quaternions, I managed to solve the problem using this fact but I don't see why this fact holds at all, specifically I managed to solve it for $p=2$ or $p\equiv 1 \pmod 4$ in a trivial manner, but for the other primes I don't quite see how that would work, I assume it can be solved using some results from quadractic residues but I am not sure.

Does this answer your question? Show that for any prime $ p $, there are integers $ x $ and $ y $ such that $ p|(x^{2} + y^{2} + 1) $. . Found using Approach0. There's also Quadratic Congruence for every prime here, plus the AoPS thread For every prime number. — John Omielan, May 22 '22 at 21:47

score 4 · Accepted Answer · answered May 22 '22 at 20:02

4

It is well known that there are exactly $\frac{p+1}{2}$ quadratic residues modulo $p$ (including $0$) for any odd prime $p$. Therefore, $a^2$ can take $\frac{p+1}{2}$ distinct values modulo $p.$ The same holds for $-b^2 - 1.$ Now, we have $p+1$ values modulo $p$ in total. By the pigeonhole principle, there is at least one pair of these values which are congruent. This observation concludes the proof.

answered May 22 '22 at 20:02

Fikilis

703

2

And in the same way, for every $c \bmod p$ there are $a$ and $b$ such that $a^2 + b^2 \equiv c \bmod p$. – KCd May 22 '22 at 21:07

For every prime p there is a sum of squares congruent to -1 mod p

1 Answers1