Elliptic-curve point count over a finite field

If $\alpha ,\beta$ are the roots of $T^2-aT+q$, where $a=q+1-\#E({\mathbb{F}}_q)$, then

For an elliptic curve over ${\mathbb{F}}_q$, the Frobenius isogeny has characteristic polynomial $T^2-tT+q$. Taking traces of its powers gives this recurrence. If $\alpha ,\beta$ are the roots, then $t_n={\alpha }^n+{\beta }^n$ and $\#E({\mathbb{F}}_{q^n})=q^n+1-t_n$. The Hasse bound implies $|\alpha |=|\beta |=\sqrt{q}$, including the repeated-root case.

At an odd good prime, use a model $y^2=x^3-d^{2}x$ with $d$ a unit. If $p\equiv 3(\mathrm{mod}4)$, pairing $x$ with $-x$ cancels their Legendre symbols, so the trace is zero. If $p\equiv 1(\mathrm{mod}4)$, the four distinct rational 2-torsion points force the group order to be divisible by four, whereas $p+1$ is two modulo four. The trace cannot vanish. This proves the converse without an explicit complex-multiplication character-sum evaluation.

For an elliptic curve over a finite field of characteristic $p$, its rational-point group is finite and abelian. Prime-to-characteristic geometric torsion bounds every other prime-torsion dimension by two. Multiplication by $p$ has degree $p^2$ and inseparable degree at least $p$, so the $p$-torsion dimension is at most one. The structure theorem for finite abelian groups therefore gives two cyclic factors with $m\mid n$ and $p\nmid m$.

For odd $p$ and $k\not\equiv 0(\mathrm{mod}p)$, take $E:y^2=x^3+kx$. If $p\equiv 3(\mathrm{mod}4)$, pairing $x$ with $-x$ cancels the Legendre symbols. If $p\equiv 1(\mathrm{mod}4)$, the coefficient formula for trace of Frobenius modulo p givesThe binomial coefficient is nonzero because every factorial involved is shorter than $p$. Thus the Trace of Frobenius is not zero in the second case.

For an elliptic curve over ${\mathbb{F}}_p$, put $N=\#E({\mathbb{F}}_p)$ and $a=p+1-N$. The trace of the square of an elliptic-curve endomorphism gives $\mathrm{tr}({\pi }^2)=a^2-2p$ for the Frobenius isogeny. Therefore $\#E({\mathbb{F}}_{p^2})=p^2+1-a^2+2p=N(2p+2-N)$.

For $E:y^2=x^3-x-1$ over ${\mathbb{F}}_3$, the Trace of Frobenius is three andIn particular, $\#E({\mathbb{F}}_{3^r})=3^r+1$ exactly when $r\equiv 3(\mathrm{mod}6)$.