When is the sum of two quadratic residues modulo a prime again a quadratic residue?

Question

Let $p$ be an odd prime. I am interested in how many quadratic residues $a$ sre there such that $a+1$ is also a quadratic residue modulo $p$. I am sure that this number is $$ \frac{p-6+\text{mod}(p,4)}{4}, $$ but I have neither proof nor reference. It is a particular case of the question in the title: if $a$ and $b$ are quadratic residues modulo $p$, when is $a+b$ also a quadratic residue modulo $p$?

I came into this question when counting the number of diophantine $2$-tuples modulo $p$, that is, the number of pairs $\{ a,b\}\subset \mathbb{Z}^*_p$ such that $ab+1$ is a quadratic residue modulo $p$.

Answer 1

Here's a copy-paste of something I wrote up a while ago:

Lemma: Let $q$ be odd, and let $Q$ be the set of quadratic residues (including $0$) in $\mathbb F_q$. Then the number of elements $s_q(c)$ in $\{x^2+c|x \in \mathbb{F}_q\} \cap Q$ is given by \begin{array}{|c|c|c|} \hline & c \in Q & c \notin Q \\ \hline -1 \in Q & \frac{q+3}{4} & \frac{q-1}{4} \\ \hline -1 \notin Q & \frac{q+1}{4} & \frac{q+1}{4} \\ \hline \end{array}

Proof: If, for $x,y,c\in \mathbb{F}_q,\ c \neq 0$ we have $x^2+c=y^2$, then $c=y^2-x^2=(y-x)(y+x)$. Now for all the $q-1$ elements $d\in \mathbb{F}_q^{\ast}$, we can let $y-x=d$ and $y+x=\frac{c}{d}$. But the pairs $(d,\frac{c}{d}),(-d,\frac{c}{-d}),(\frac{c}{d},d),(\frac{c}{-d},-d)$ all give the same value of $y^2=\frac{1}{4}(d+c/d)^2$. Also, as $q$ is odd, $d\neq -d\ \forall d$. But if $c\in Q$, for $2$ values of $d$ we have $d=\frac{c}{d}$ and if $-c\in Q$, for 2 values of $d$ we have $d=\frac{c}{-d}$. So we have $$ s_q(c) = \left\{ \begin{array}{rcll} \frac{\frac{q-1}{2}-2}{2}+2 & = & \frac{q+3}{4} & if\ c\in Q,\ -c\in Q \\ \frac{\frac{q-1}{2}-1}{2}+1 & = & \frac{q+1}{4} & if\ c\in Q,\ -c\notin Q \\ \frac{\frac{q-1}{2}-1}{2}+1 & = & \frac{q+1}{4} & if\ c\notin Q,\ -c\in Q \\ & & \frac{q-1}{4} & if\ c\notin Q,\ -c\notin Q \end{array} \right. $$ and hence the result.

Answer 2

It is easy to write this number (of $a$ such that $a,a+1$ are squares) in terms of the number of solutions of $x^2-y^2=1$. This is a conic which has $p+1$ projective points over the field of $p$ elements (since it is isomorphic to $\mathbb{P}^1$). It has two points at infinity, two points with $y=0$ and two or zero points with $x=0$, depending on $p \mod 4$. So you get your formula.

There is no way of telling the quadratic character of $a+b$ from that of $a,b$, but it is a square half the time.

Answer 3

To complement the answers so far let me show using Gauss sums that the number of solutions of $ ax^2+by^2=c $ in $\mathbb{F}_p$ equals $p-\left(\frac{-ab}{p}\right)$ for any $a,b,c\in\mathbb{F}_p^\times$. Indeed, this number equals $$ \frac{1}{p}\sum_n \sum_{x,y}e\left(n\frac{ax^2+by^2-c}{p}\right) = \frac{1}{p}\sum_n e\left(\frac{-nc}{p}\right) \sum_xe\left(\frac{nax^2}{p}\right)\sum_ye\left(\frac{nby^2}{p}\right),$$ where all sums are over $\mathbb{F}_p$ and $e(t)$ abbreviates $e^{2\pi i t}$. For $n\neq 0$ we have $$ \sum_xe\left(\frac{nax^2}{p}\right)\sum_ye\left(\frac{nby^2}{p}\right) = \left(\frac{na}{p}\right)\left(\frac{nb}{p}\right)\left(\sum_re\left(\frac{r^2}{p}\right)\right)^2 = \left(\frac{-ab}{p}\right)p,$$ so that the count in question equals $$ p+\left(\frac{-ab}{p}\right)\sum_{n\neq 0}e\left(\frac{-nc}{p}\right)=p-\left(\frac{-ab}{p}\right). $$

Answer 4

There is an elementary argument regarding the last problem. Denote by $N(p)$ the number of pairs of $(a,b)$ such that $a,b,a+b$ are all quadratic residues mod $p$. Hence we have $$N(p)=\frac{1}{8}\mathop{\sum\sum}_{\substack{a,b\bmod p\\(ab(a+b),p)=1}}\left(1+\left(\frac{a}{p}\right)\right)\left(1+\left(\frac{b}{p}\right)\right)\left(1+\left(\frac{a+b}{p}\right)\right)$$

$$=\frac{1}{8}\mathop{\sum\sum}_{\substack{a,b\bmod p\\(ab,p)=1}}\left(1+\left(\frac{a}{p}\right)\right)\left(1+\left(\frac{b}{p}\right)\right)\left(1+\left(\frac{a+b}{p}\right)\right)$$

$$-\frac{1}{8}\mathop{\sum\sum}_{\substack{a,b\bmod p\\(ab,p)=1,p|a+b}}\left(1+\left(\frac{a}{p}\right)\right)\left(1+\left(\frac{b}{p}\right)\right).$$

Clearly, the second term is just \begin{align*}&-\frac{1}{8}\sum_{\substack{a\bmod p\\(a,p)=1}}\left(1+\left(\frac{a}{p}\right)\right)\left(1+\left(\frac{-a}{p}\right)\right)=\frac{1}{8}-\frac{p}{8}\left(1+\left(\frac{-1}{p}\right)\right).\end{align*} And for the first term, we are required to investigate the quantity \begin{align*}L:=\mathop{\sum\sum}_{\substack{a,b\bmod p\\(ab,p)=1}}\left(\frac{ab(a+b)}{p}\right).\end{align*} In fact we have

$$L:=\mathop{\sum\sum}_{\substack{a,b\bmod p\\(ab,p)=1}}\left(\frac{ba^2+b^2a}{p}\right) =\mathop{\sum\sum}_{\substack{a,b\bmod p\\(ab,p)=1}}\left(\frac{b(a+\overline{2}b)^2-\overline{4}b^3}{p}\right)$$

$$=\mathop{\sum\sum}_{a,b\bmod p}\left(\frac{ba^2-\overline{4}b^3}{p}\right)$$

$$=\sum_{b\bmod p}\left(\frac{b}{p}\right)\sum_{a\bmod p}\left(\frac{a^2-\overline{4}b^2}{p}\right)$$

$$=\sum_{b\bmod p}\left(\frac{b}{p}\right)\sum_{a\bmod p}\left(\frac{a^2-1}{p}\right)=0.$$

The other terms could be computed in a similar way. Hence we can deduce that \begin{align*}N(p)=\frac{1}{8}(p-1)^2-\frac{p}{8}\left(1+\left(\frac{-1}{p}\right)\right)+\frac{1}{8}.\end{align*}