5

So we obviously we want $ x^{2} + y^{2} + 1 \equiv 0 ~ (\text{mod} ~ p) $.

I haven’t learned much about quadratic congruences, so I don’t really know how to go forward. I suppose you can write it as $ x^{2} \equiv -1 - y^{2} ~ (\text{mod} ~ p) $, but again, I’m not sure where to go. I know about the Legendre symbol and quadratic residues, which I know are involved in this question, but I don’t know how to apply what I know. :(

Berrick Caleb Fillmore
  • 5,269

2 Answers2

12

Let: $$A=\{x^2|x\in \Bbb Z_p\},\ \ \ \ \ \ \ B=\{-(1+y^2)|y\in \Bbb Z_p\}$$

it is known that $$|A|=|B|=\frac{p+1}{2}$$ (maybe you can try to prove this ), if $A\cap B=\varnothing$ then $|A\cup B|=|A|+|B|=p+1>|\Bbb Z_p |$ which is impossible. as a conclusion $A\cap B$ is not empty and you're done.

Elaqqad
  • 13,725
  • In the contradiction step, do you mean union instead of intersection? – shardulc May 01 '15 at 18:00
  • Yes you're right, in order to prove the claim $|A|=|B|=\frac{p+1}{2}$, can be done in two steps , first notice that $|A|=|B|$ they have the same cardinals which is the number of squares in $\Bbb Z_p$ ( bujection $A:\to B\ \ x\to -(1+x)$) and in order to find the number of squares you can look in the internet for "the number of squares in $\Bbb Z_p$ " don't forget that $0$ is olso a square and good luck – Elaqqad May 01 '15 at 18:12
  • 6
    +1. Nice elegant argument. In fact, this shows that for any prime $p$ and any $k \in \mathbb{Z}_p$, there exists $x,y$ such that $x^2+y^2 \equiv k \pmod{p}$. – Adhvaitha May 01 '15 at 18:17
  • Yes this is correct – Elaqqad May 01 '15 at 18:20
  • I know that there are (p-1)/2 squares in (z/pz)* and (p+1)/2 squares in (z/pz), but how does knowing that let me show there are always solutions for this congruence? :( I'm afraid I have never done union and intersection kinds of proofs before, so I'm not sure I get your answer Elaqqad. Also, @user17762, If I am right in assuming that Zp are the positive integers, how does that work for my needing k=-1? Thank you so much for your help! –  May 04 '15 at 16:49
  • You have $\frac{p+1}{2}$ elements in $A$ and $\frac{p+1}{2}$ elements in $B$ and because $A\cup B\subset Z/pZ$ of cardinal $p$ this means that there exist an element $t$ which is in both $A$ and $B$ let denote this element $t$ we have $t=x^2\mod p$ for some $x$ and you have $t=-(1+y^2)$ for some $y$ and hence $x^2+y^2=1\mod p$ for some $x$ and $y$ – Elaqqad May 04 '15 at 16:52
1

The number of quadratic residues $\bmod p$ (prime), $|\mathcal{QR}| = \dfrac{p+1}{2}\qquad$ [1].

If we form pairs of residues $(a,b)$ such that $a+b = p-1$, we have $\frac{p-1}{2}$ distinct pairs plus $\frac{p-1}{2}$ paired with itself.

If $\frac{p-1}{2}$ is a quadratic residue, we can form the required expression using this. Otherwise, by the pigeonhole principle, one of the other residue pairs must both consist of quadratic residues - so there is $(x,y)$ with $x^2\equiv a$ and $y^2\equiv b\bmod p$. This gives the required assurance that we can form $x^2+y^2 \equiv -1 \bmod p$.

[1] The number of quadratic residues can be seen as a consequence of the existence of primitive roots. If $g$ is a primitive root $\bmod p$, this means that the smallest $k$ for which $g^k\equiv 1\bmod p$ is $k=p-1$. Now all the even powers of $g$, $(g^{2j})$ are quadratic residues since $g^{2j} \equiv (g^j)^2 \bmod p$, giving $(p-1)/2$ quadratic residues. Then there's one more: $0$ is a quadratic residue since $p^2\equiv 0 \bmod p$, so $(p+1)/2$ quadratic residues all together.

Joffan
  • 39,627