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.

I have heard somewhere that for all primes $p$, for all $k$, there exist $x, y$ s.t. $x^2 + y^2\equiv k \pmod{p}$? I recall that the proof is very elementary, but I can't remember such a proof. How would one prove this? One way is to use Cauchy-Davenport, but I don't think that this is the simplest solution.

share|improve this question
    
    
You can use Legendre symbol as used in this post: math.stackexchange.com/questions/398200/… –  Aran Komatsuzaki Aug 9 at 9:54

2 Answers 2

up vote 7 down vote accepted

There are $(p+1)/2$ squares mod $p$ [if $p$ is odd; the case $p=2$ is left for the reader], so $(p+1)/2$ numbers $x^2$, and $(p+1)/2$ numbers $k-y^2$, so the two sets must overlap, and where they overlap you get $x^2=k-y^2\pmod p$.

share|improve this answer
    
Blast! You beat me. But I swear I'm not adept enough with Latex to type my answer up within 5 minutes! –  PrimeRibeyeDeal Aug 9 at 12:47
1  
You typed 6 paragraphs. I typed 3 lines. –  Gerry Myerson Aug 9 at 12:48

Since you're using a combinatorics tag, let's solve this using the pigeonhole principle on elements of $\mathbb{F}_p$.

Since the $p=2$ case is easy, let's assume that $p>2$.

Define $S := \{x^2|x\in\mathbb{F}_p\}$ to be the set of squares in $\mathbb{F}_p$, and $T := k - S = \{k - x^2|x\in\mathbb{F}_p\}$ to be the set of squares shifted by $k$. Note that $S$ and $T$ have the same number of elements, which I claim is $\frac{p+1}{2}$.

We momentarily disregard $0$. The map $x\mapsto x^2$ is a $2$-to-$1$ function from $\mathbb{F}_p^\mathrm{x}$ to itself. So the image of the squaring function on $\mathbb{F}_p^\mathrm{x}$ must have $\frac{1}{2}\cdot\#\mathbb{F}_p^\mathrm{x} = \frac{p-1}{2}$ elements. But the image of this function is exactly the set $S$ minus the $0$ element. So $\#S = \#T = \frac{p+1}{2}$.

This situation is akin to when two stars of enormous but stable mass come into proximity with one another and the total sum of their mass has reached critical level and then they implode, forming a neutron star.

In other words, the pigeonhole principle gives us an neutron star $\alpha$ that must be contained in both $S$ and $T$. So $$\alpha = x^2 = k - y^2$$ And then from this we get $$x^2 + y^2 = k$$

share|improve this answer

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.