Are you sure? If $k=3, p=13$, then $S$ is the set of non-negative integers $\le 6$ which are of the form $10n^3$, so $S=\{0,1\}$ which does not satisfy the equation $0^2+1^2=13$...

Tintarn wrote: Are you sure? If $k=3, p=13$, then $S$ is the set of non-negative integers $\le 6$ which are of the form $10n^3$, so $S=\{0,1\}$ which does not satisfy the equation $0^2+1^2=13$... Edited

Isn't it wrong again? What changed?

toto1234567890 wrote: Isn't it wrong again? What changed? I added the 'residue mod p' part..

lminsl wrote: toto1234567890 wrote: Isn't it wrong again? What changed? I added the 'residue mod p' part.. Oh... ok

This is a famous result of Gauss in [1828]. If we write $p=x^2+y^2, x \equiv1(\mod 4), y\equiv0(\mod 2)$ Then, $ \binom{2k}{k}\equiv 2x(\mod p) $, and furthermore, $ \binom{2k}{k}\equiv \frac{2^{p-1}+1}{2}(2x-\frac{p}{2x})(\mod p^2) $. I wonder why they put it here...

Well, maybe we can think of $ f(n)=\sum_{i=0}^{p-1}\left ( \frac{x(x^2+n)}{p} \right ) $. And if we pick two $ a,b $ such that$ \left ( \frac{a}{p} \right )=1, \left ( \frac{b}{p} \right )=-1$, then $ \left ( \frac{1}{2}f(a) \right )^2+\left ( \frac{1}{2}f(b) \right )^2=p $ You can easily show that this is what we wanted.

For those interested in the proof of Gauss' theorem, you can find it in here.

fattypiggy123 wrote: For those interested in the proof of Gauss' theorem, you can find it in here. Well, this makes sense then. My solution above just seems to have nothing to do with anything that at least can make me nod.

toto1234567890 wrote: You can easily show that this is what we wanted. Well, you could demonstrate the calculation here, if it is that clear you think. It didn't make sense to me since usually summation of quadratic residue of cubic polynomial requires some theory of elliptic curves...

IsoLyS wrote: toto1234567890 wrote: You can easily show that this is what we wanted. Well, you could demonstrate the calculation here, if it is that clear you think. It didn't make sense to me since usually summation of quadratic residue of cubic polynomial requires some theory of elliptic curves... $f(ax^2) \equiv \left ( \frac{x}{p} \right )f(a)$ -> $ f(a)^2+f(b)^2=\frac{2}{p-1}\sum_{k=0}^{p-1}f(k)^2 $. $ \sum_{k=0}^{p-1}f(k)^2=\sum_{i=0}^{p-1}\sum_{j=0}^{p-1}f(i)f(j)=\sum_{i=0}^{p-1}\sum_{j=0}^{p-1}\left ( \frac{ij}{p} \right )\sum_{n=0}^{p-1}\left ( \frac{(i^2+n)(j^2+n)}{p} \right )=p(2p-2)-\sum_{i=0}^{p-1}\sum_{j=0}^{p-1}\left ( \frac{ij}{p} \right )=2p(p-1) $ (because $ \sum_{n=0}^{p-1}\left ( \frac{(i^2+n)(j^2+n)}{p} \right ) $ is $ p-1 : i^2 \equiv j^2 (\mod p ) $ or $ -1 : else $) So, we are left with proving that $ \binom{2k}{k} $ comes out of somewhere. (This was my motive actually.) $ f(a)=\sum_{i=0}^{p-1}\left ( \frac{x(x^2+a)}{p} \right ) \equiv \sum_{i=0}^{p-1} (x^3+nx)^{2k} (\mod p) $ and now You can see why $ \binom{2k}{k} $ comes out of here.

See also PEN P17. Original version of this problem required sum of another type of quadratic residues.

IsoLyS wrote: See also PEN P17. Original version of this problem required sum of another type of quadratic residues. Yeah it is

Lemma: $\sum\limits_{x=0}^{p-1} \left( \frac{x^2+a}{p} \right) = p-1$ if $p\mid a$ and $-1$ otherwise. Proof: When $p\mid a$ this is clear. We count the number of solutions to $y^2-x^2\equiv a(\bmod\; p)$. Note this is equivalent to $(y-x)(y+x)\equiv a(\bmod\; p)$. If $p\nmid a$ there are $p-1$ ways to pick $(y-x,y+x)$ so there are $\frac{p-1}{2}$ solutions to $x^2+a\equiv y^2(\bmod\; p)$. If $\left( \frac{-a}{p} \right)=1$ then setting $x^2\equiv -a(\bmod\; p)$ produces one special solution. In this case there are $\frac{p-3}{2}$ solutions to $\left( \frac{x^2+a}{p} \right)=1$ and $\frac{p-1}{2}$ solutions to $\left( \frac{x^2+a}{p} \right)=-1$ The case where $\left( \frac{-a}{p} \right)=-1$ is similar. First notice $\sum\limits_{x=0}^{p-1} \left( \frac{x+x^3}{p} \right) \equiv \sum\limits_{x=0}^{p-1} (x+x^3)^{\frac{p-1}{2}} \equiv -\binom{2k}{k} (\bmod\; p)$ Now we consider $\sum\limits_{x=0}^{p-1} \left( \frac{x+x^3}{p} \right)$. We want to find out interesting properties about its square knowing it's connected to the equation $m^2+n^2=p$. Let $f(a)=\sum\limits_{x=0}^{p-1} \left( \frac{ax+x^3}{p} \right)$. Claim: $\sum\limits_{a=1}^{p-1} f(a)^2=2p(p-1)$. Proof: $\sum\limits_{a=1}^{p-1} f(a)^2=\sum\limits_{1\le a,x,y\le p-1} \left(\frac{x^3+ax}{p} \right) \left(\frac{y^3+ay}{p} \right) = \sum\limits_{1\le n,x\le p-1} \left(\frac np \right) \sum\limits_{a=1}^{p-1} \left(\frac{x^2+a}{p} \right) \left(\frac{(\frac nx)^2+a}{p} \right)$ (where $n\equiv xy$ mod p) Observe $\sum\limits_{a=1}^{p-1} \left(\frac{x^2+a}{p} \right) \left(\frac{(\frac nx)^2+a}{p} \right) = -1+\sum\limits_{a=0}^{p-1} \left(\frac{a^2+a(x^2+n^2/x^2)+n^2}{p} \right) =$ $$-1+\sum\limits_{a=0}^{p-1} \left(\frac{(a+\frac{x^2}{2}+\frac{n^2}{2x^2})^2-(\frac{x^2}{2}-\frac{n^2}{2x^2})^2}{p} \right)$$ This means if $p\nmid x^4-n^2$ then this sum is $-2$. Otherwise, this is $p-2$. This means $\sum\limits_{a,x=1}^{p-1} \left(\frac{x^2+a}{p} \right) \left(\frac{(\frac nx)^2+a}{p} \right)$ is $4(p-2)-2(p-5)$ if $\left( \frac np \right)=1$ and $-2(p-1)$ otherwise. This means the entire sum is $\frac{p-1}{2}(4(p-2)-2(p-5)+2(p-1)=2p(p-1)$ Note $f(a)^2\equiv \binom{2k}{k}^2\left( \frac ap \right) (\bmod\; p)$. This implies if $\left( \frac ap \right)=1, \left( \frac bp \right)=-1$ then $f(a)^2+f(b)^2=4p$. Thus, $(\frac 12 f(a))^2+(\frac 12 f(b))^2=p$, as desired.