1

I asked this question a couple days ago: Show that for any prime $ p $, there are integers $ x $ and $ y $ such that $ p|(x^{2} + y^{2} + 1) $. But I asked it as a guest, and I could not comment on the answers I got as I did not have enough reputation.

I have found a proof from Warwick University that will help me answer this question, but there is one sentence I am unsure of. If anybody could help me out on it, that would be amazing!

Here it is:

There are $\frac{p+1}{2}$ numbers of the form $x^2 \pmod{\!p}$. There are $\frac{p+1}{2}$ numbers of the form $-1-y^2 \pmod{\!p}$ (because to get the numbers of the form $-1-y^2$, multiply the squares by $-1$ and subtract $1$… this will not change how many there are). There are exactly $p$ numbers mod $p$. Note that $\frac{p+1}{2}$ is more than half of $p$. So the set of numbers of the form $x^2$ and those of the form $\frac{p+1}{2}$ must have at least one common element (if not, we will have too many distinct numbers mod $p$). So there are some $x$ and $y$ such that $x^2\equiv -1-y^2 \pmod{\!p}$. Thus $x^2 + y^2 +1\equiv 0 \pmod{\!p}$.

I understand it up until the bolded sentence. Did they mean to write numbers of the form $\frac{p+1}{2}$? Or did they instead mean numbers of the form $-1-y^2$?

No matter what they meant, would anybody be able to explain more how having at least one overlapping element in both sets tells you that solutions to that congruence exists? How did they come to that conclusion that there is a common element? What would happen if there wasn't a common element? Thank you!

Community
  • 1
user236043
  • 11
  • I think that they meant "of the form $-1-y^2$" and this is axactly what I wrote in my answer for your question – Elaqqad May 08 '15 at 14:36

2 Answers2

4

As you have guessed, there is an error (maybe just a typo) in that sentence. It should be

So the set of numbers of the form $x^2$ and those of the form $-1-y^2$ must have at least one common element (if not, we will have too many distinct numbers mod $p$).

The point is that if you give all possible values to $x$ modulo $p$, all possible values to $y$ and then work out all the values of $x^2$ and of $-1-y^2$ modulo $p$, you will get $\frac{p+1}2$ different values for $x^2$ and $\frac{p+1}2$ different values for $-1-y^2$, that's $p+1$ answers altogether.

But you cannot get $p+1$ different answers as there are only $p$ possibilities modulo $p$. So two of your answers must be the same: either

  • two of the $x^2$ values are the same; or
  • two of the $-1-y^2$ values are the same; or
  • an $x^2$ value is the same as a $-1-y^2$ value.

But we have already noted that the first two of these options are impossible, so the third one must be true.

If it helps, look at a specific example, say $p=7$. There are four possible values of $x^2$, namely $$0,\ 1,\ 4,\ 2.$$ Now without working them out, you can see that there will be four values of $-1-y^2$: so we will have eight numbers written down: so two of them must coincide. To confirm this, the values of $-1-y^2$ are $$-1,\ -2,\ -5,\ -3,$$ that is, $$6,\ 5, 2,\ 4,$$ and you can see that the result $2$ occurs twice. (In fact, so does the result $4$, giving another possible solution.)

Exercise: show that the "other possible solution" is really the same solution.

abiessu
  • 8,115
David
  • 82,662
0

A more general version of this result can be found in Herstein's : Topics in Algebra text. Kindly see Lemma 7.1.7 Page $359$. The result states that

  • If $F$ is a finite fied and $\alpha \neq 0$ and $\beta \neq 0$ are two elements of $F$ then we can find elements $a$ and $b$ in $F$ such that $1 + a \cdot\alpha^{2} + b \cdot \beta^{2}=0$.
C.S.
  • 5,528
  • This is not really a generalisation because this says only that $1,\alpha^2,\beta^2$ are dependant which is not really the same thing as saying that there exists some $x,y$ such that $1+x^2+y^2=0$ (it's correct but what I mean is that your answer is not a generalisation it's another separte result ) – Elaqqad May 08 '15 at 14:35