Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $p$ be a prime number. Prove that exists $a,b \in \mathbb{Z}$ such that $p|a^2+b^2+1$. What I've tried:

If $p \equiv 1 \mod 4$, we put $b=0$ and the condition is simply $a^2 \equiv -1 \mod p$ which has a solution by basic quadratic reprocity.

If $p \equiv 3 \mod 4$, I did not see anything simple that might work and some examples don't show any apparent pattern ($7|3^2+2^2+1,$ $19|6^2+1^2+1$, $23 | 6^2+3^2+1$, etc.)

Thank you.

share|cite|improve this question
up vote 10 down vote accepted

The result is obvious for $p=2$, and as you point out it is straightforward for primes of the form $4k+1$. But we give a proof that works for all odd primes.

Let $A$ be the set $\left\{0^2,1^2,2^2,\dots, \left(\frac{p-1}{2}\right)^2\right\}$. Let $B$ be the set $\left\{-1-0^2, -1-1^2, -1-2^2, \dots, -1-\left(\frac{p-1}{2}\right)^2\right\}$.

It is easy to show that any two elements of $A$ are incongruent modulo $p$, as are any two elements of $B$.

But the number of elements of $A$ is $\frac{p-1}{2}+1$, as is the number of elements of $B$.

The sum of the sizes of $A$ and $B$ is $p+1\gt p$. Thus by the Pigeonhole Principle there exist $x\in A$, $y\in B$ such that $x\equiv y\pmod{p}$.

It follows that there is an $a$ and a $b$ such that $a^2\equiv -1-b^2\pmod{p}$. This is what we wanted to prove.

share|cite|improve this answer
Uhm, don't you mean $\frac{p-1}2$ everywhere you write $\frac{q-1}2$? – user2345215 Feb 28 '14 at 1:35
Yws, thank you. – André Nicolas Feb 28 '14 at 2:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.