For a given odd prime $p$ (with $p \mod 4 = 1$) I've being amusing myself to add any qr and any qnr. The result is sometimes a qr and sometimes a qnr, but what I found out is that exactly half of all the possible sums are qr and the other half are qnr. I've tried to write the qr as $a^{2i}$ (with $a$ a primitive root) and the qnr as $a^{2j+1}$, but $a^{2i} + a^{2j+1}$ leads nowhere, is it possible to prove this?

• I was only working with nonzero elements. – Marc Bogaerts Dec 20 '16 at 17:56
• Example $p = 13$, following tuples when added give a qr : $$[ 1, 2 ], [ 1, 8 ], [ 1, 11 ], [ 3, 6 ], [ 3, 7 ], [ 3, 11 ], [ 4, 5 ], [ 4, 6 ], [ 4, 8 ], [ 9, 5 ], [ 9, 7 ], [ 9, 8 ], [ 10, 2 ], [ 10, 6 ], [ 10, 7 ], [ 12, 2 ], [ 12, 5 ], [ 12, 11 ]$$ – Marc Bogaerts Dec 20 '16 at 18:02
• Remarkably every qr occurs 3 times on the left and every qnr occurs 3 times on the right. – Marc Bogaerts Dec 20 '16 at 18:14

Thanks to Andreas Caranti for the proof; his deleted argument contains most of this argument. I decided to finish the proof it for myself, and to avoid having to throw my work away I post it here. @Andreas: If you wish to undelete your answer and finish it, I'd be happy to remove this answer.

Let $F:=\Bbb{Z}/p\Bbb{Z}$ so that $F^{\times}$ is cyclic of order $p-1$. Let $A$ and $B$ denote the sets of quadratic residues and nonresidues, respectively, and fix some $t\in B$ so that $$B=tA=\{ta:\ a\in A\}.$$ Let $a\in A$ and $b\in B$. There exist $x,y\in F^{\times}$ so that $a=x^2$ and $b=y^2t$, and $x$ and $y$ are determined by $a$ and $b$ up to sign. Let $c:=x^2+y^2t$. In the ring $E:=F[\sqrt{-t}]$ we can write this as $$c=(x+y\sqrt{-t})(x-y\sqrt{-t}),$$ where $E\cong F[X]/(X^2+t)$ is a field of order $p^2$ because $X^2+t$ is irreducible as $-t$ is not a quadratic residue; we chose $t\in B$ and we have $-1\in A$ because $p\equiv1\pmod{4}$, so $-t\in B$.

In fact the identity above shows that $c$ is the norm of $x+y\sqrt{-t}\in E$, where the norm $$\mathcal{N}:\ E^{\times}\ \longrightarrow\ F^{\times}:\ z\ \longmapsto\ z\cdot z^p,$$ is a group homomorphism. From $\sqrt{-t}^p=-\sqrt{-t}$ it follows that \begin{align} \mathcal{N}(x+y\sqrt{-t}) &=(x+y\sqrt{-t})(x+y\sqrt{-t})^p\\ &=(x+y\sqrt{-t})(x^p+y^p\sqrt{-t}^p)\\ &=(x+y\sqrt{-t})(x-y\sqrt{-t}), \end{align} which shows that $c=\mathcal{N}(x+\sqrt{-t})$. Note that the norm is surjective because $$\ker\mathcal{N}=\{z\in E^{\times}:\ z^{p+1}=1\},$$ is a subgroup of order $p+1$ of the cyclic group $E^{\times}$ of order $p^2-1$, so the image of $\mathcal{N}$ is of order $$\frac{p^2-1}{p+1}=p-1=|F^{\times}|.$$ Now because $\mathcal{N}$ is a group homomorphism the elements of norm $c$ form a coset of the kernel of $\mathcal{N}$, so in particular for every $c\in F^{\times}$ the number of pairs $x,y\in F$ with $\mathcal{N}(x+y\sqrt{-t})=c$ is the same. It follows that the number of pairs $(a,b)\in A\times B$ with $a+b=c$ is the same for every $c$.

Do note that in every coset of $\ker\mathcal{N}$ in $E^{\times}$ there are precisely two elements that do not correspond to pairs in $A\times B$; these are the elements of the form $x+y\sqrt{-t}$ with $xy=0$, i.e. $x=0$ or $y=0$. Because there are precisely two such elements in every coset, the number of solutions to $a+b=c$ with $(a,b)\in A\times B$ is still the same for every $c\in F^{\times}$; there are $\frac{p-1}{4}$ pairs for every $c\in F^{\times}$.

• Nice proof! I had difficulties to see why $\sqrt{t}^p=-\sqrt{t}$, but thats because $-\sqrt{t}$ is the conjugate of the root $\sqrt{t}$ and the Galois group of $E/F$ is cyclic of order $2$ and generated by the Frobenius automorphism. Kudos for Andreas, although I don't see why he deleted his answer. – Marc Bogaerts Dec 21 '16 at 11:46
• That's a nicer way to see it :) I tried to avoid Galois theory, though it does smooth things out a bit. But a computation also shows that $$\sqrt{t}^p=t^{\frac{p-1}{2}}\cdot\sqrt{t}=-1\cdot\sqrt{t},$$ because $t$ is not a quadratic residue mod $p$. – Servaes Dec 21 '16 at 13:57
• This is maybe a shorter proof (I'll take your notations). Let $k$ be any element $\in B$. If we denote by $P$ those elements of $A \times B$ whose sum is a qr and by $N$ those whose sum is a qnr. Then the map $A \rightarrow B : (a,b) \mapsto (kb, ka)$ is a bijection. – Marc Bogaerts Dec 21 '16 at 14:34
• I think you mean the map $P\ \longrightarrow\ N:\ (a,b)\ \longmapsto\ (kb,ka)$? Yes, this is a much shorter proof :) But as you see there is much more to find here, I'm glad your question pointed this out to me! – Servaes Dec 21 '16 at 14:39
• Indeed, $P$ & $N$, I make a lot of mistakes. BTW your answer has learned me a lot. – Marc Bogaerts Dec 21 '16 at 15:02