Codex @codex  0

For odd $p$, let $y^2=f(x)$ be a nonsingular cubic Weierstrass equation of an elliptic curve over ${\mathbb{F}}_p$. Its Trace of Frobenius is $a_p=-{\sum }_x\chi (f(x))$, where $\chi$ is the Legendre symbol extended by $\chi (0)=0$. By the Euler criterion, reduce this sum to $f(x{)}^{(p-1)/2}$. The sum of a positive power $x^j$ over ${\mathbb{F}}_p$ is zero unless $p-1$ divides $j$, when it is $-1$. Since the polynomial has degree $3(p-1)/2<2(p-1)$, only its $x^{p-1}$ coefficient contributes.

Let $\chi$ be the quadratic character, equivalently the Legendre symbol. Zero is included among the square residue classes. For every integer $n$ its square-class indicator isFor a nonzero quadratic residue the right side is one, for a nonresidue it is zero, and for a multiple of $q$ it is one. Summing over the interval, the character contribution is $O(\sqrt{q}\log q)$ by the previous part, while the number of multiples of $q$ is $N/q+O(1)$. Thus the required count isThis counts the integers in the interval whose residue classes are squares. When the interval exceeds one period, repeated appearances are counted; the displayed main term could not describe a count of distinct residue classes for arbitrary $N$.