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?

  • $\begingroup$ I was only working with nonzero elements. $\endgroup$ – Marc Bogaerts Dec 20 '16 at 17:56
  • $\begingroup$ 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 ]$$ $\endgroup$ – Marc Bogaerts Dec 20 '16 at 18:02
  • $\begingroup$ Remarkably every qr occurs 3 times on the left and every qnr occurs 3 times on the right. $\endgroup$ – 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}$.

  • 1
    $\begingroup$ 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. $\endgroup$ – Marc Bogaerts Dec 21 '16 at 11:46
  • $\begingroup$ 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$. $\endgroup$ – Servaes Dec 21 '16 at 13:57
  • $\begingroup$ 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. $\endgroup$ – Marc Bogaerts Dec 21 '16 at 14:34
  • $\begingroup$ 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! $\endgroup$ – Servaes Dec 21 '16 at 14:39
  • $\begingroup$ Indeed, $P$ & $N$, I make a lot of mistakes. BTW your answer has learned me a lot. $\endgroup$ – Marc Bogaerts Dec 21 '16 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.