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$.
Best Answer
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.