Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

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

Your Answer

 
discard

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.