As we know, if $p$ is a prime, then $p$ has $\frac{p+1}{2}$ quadratic residues. Consider the set $$A = \{k^2 - 4: k = 0, 1, \ldots, p-1\}$$ where $p$ is a prime of the form $4k+3$.
How many quadratic residues are there in $A$?
I tried with small primes such as $p = 7, 11, 23$ and I guess the answer is $\frac{p+1}{4}$, but I cannot prove it.
Thank you very much.
On
This isn't a complete answer, just an expansion on my comment.
$$\sum_{t=0}^{p-1}e^{2\pi i(k^2-4-z^2)t/p}$$ is $p$ if $k^2-4\equiv z^2\bmod p$ and zero otherwise. So $$\sum_{z=0}^{p-1}\sum_{t=0}^{p-1}e^{2\pi i(k^2-4-z^2)t/p}$$ is $2p$ if $k^2-4$ is a nonzero quadratic residue modulo $p$, it's $p$ if $k^2-4\equiv0\bmod p$ (that is, if $k\equiv\pm2\bmod p$), and otherwise it's zero. So $${1\over p}\sum_{k=0}^{p-1}\sum_{z=0}^{p-1}\sum_{t=0}^{p-1}e^{2\pi i(k^2-4-z^2)t/p}$$ gives $2$ plus twice the number of values of $k$ such that $k^2-4$ is a nonzero quadratic residue.
When $t=0$, the sum on $k$ and $z$ is $p^2$, so we get $$p+{1\over p}\sum_{t=1}^{p-1}e^{-8\pi it/p}\sum_{k=0}^{p-1}e^{2\pi itk^2/p}\sum_{z=0}^{p-1}e^{-2\pi itz^2/p}$$ Now the sums on $k$ and $z$ are quadratic Gauss sums, whose values are well-known and easily found in texts and on websites. They depend on the residue of $p$ modulo $4$, and on whether $t$ and $-t$ are quadratic residues modulo $p$.
The congruence $k^2 - 4 \equiv x^2 \bmod p$ is solvable if and only if $(k,x)$ is an ${\mathbb F}_p$-rational point on the curve $K^2 - X^2 = 4$. Such curves are easily parametrized. The simplest way of doing so is writing it in the form $(K-X)(K+X) = 4$ and setting $K-X = a$, $K + X = \frac{4}a$. Finally observe that $(k,x)$ and $(k,-x)$ correspond to the same residue.