When is the sum of two quadratic residues modulo a prime again a quadratic residue? 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$.
 A: 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.
A: 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). $$
A: 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*}
A: 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. 
