Does there exist an elliptic curve $E$ such that $\#E(\Bbb{F}_{q^2})=(q+1)^2$ for all prime powers $q$? The following (paraphrased) question is a homework exercise for a course on elliptic curves:

Let $p\not\equiv1\pmod{12}$ be a prime number and let $q=p^k$. Show that there exists an elliptic curve $E$ such that $\#E(\Bbb{F}_{q^2})=(q+1)^2$.

This is not very difficult to show. If $k$ is odd, for $p\equiv2\pmod3$ the curve given by $y^2-y=x^3$ will do, and for $p\equiv3\pmod4$ the curve given by $y^2=x^3-x$ will do. For $k$ even, their quadratic twists will do. The case $p\equiv1\pmod{12}$ seems to be more difficult; I don't have a proof. Luckily this is not part of my homework. But my question is, also not part of the homework, can we change the order of the quantifiers? That is to say:

Does there exist an elliptic curve $E$ such that $\#E(\Bbb{F}_{q^2})=(q+1)^2$ for all prime powers $q$?

Or more modestly, for all prime powers $q=p^k$ with $p\not\equiv1\pmod{12}$? Unfortunately the two curves above are not isomorphic. Otherwise I don't have much of a clue of where to look for such a curve, or whether it even exists. Any idea is very welcome.
 A: Matt E's answer uses $q=p$, with $p$ varying. I will give an argument using $q=p^k$, with $p$ fixed.
Fix a prime $p$, and let $E/\mathbb{F}_{p^2}$ be an elliptic curve such that $\#E(\mathbb{F}_{p^{2k}})=(p^k+1)^2$ for all $k\geq 1$. We can compute the zeta function of $E$:
\begin{eqnarray*}
Z_E(t)&=&\exp\left(\sum_{k\geq 1}\frac{p^{2k}+2p^k+1}{k}t^k\right)\\
&=&\exp\left(\log\frac{1}{1-p^2t}+2\log\frac{1}{1-pt}+\log\frac{1}{1-t}\right)\\
&=&\frac{1}{(1-p^2t)(1-pt)^2(1-t)}.
\end{eqnarray*}
This violates the Riemann hypothesis for finite fields (actually a theorem), which implies that roots of the denominator of $Z_E(t)$ must have absolute value $1$ or $1/p^2$.
I'm confused, because it sounds like you found an example of a curve with this property.
Edit: It sounds like the curve you wrote down has $\#E(\mathbb{F}_{p^{2k}})=(p^k+1)^2$ for $k$ odd but not for $k$ even, so there is no inconsistency. My argument shows that there is no curve $E/\mathbb{F}_{p^2}$ with $\#E(\mathbb{F}_{p^{2k}})=(p^k+1)^2$ for all $k$.
Also, in regards to my expression for the zeta function: for any curve $C/\mathbb{F}_q$, there is an equality of formal power series
$$
\sum_{D\geq 0}t^{\deg D}=\exp\left(\sum_{m\geq 1}\frac{\#C(\mathbb{F}_{q^m})}{m}t^m\right),
$$
where the sum on the left is over effective divisors $D$ on $C$ that are defined over $\mathbb{F}_q$. One sometimes sees the right hand side as the definition of $Z_C(t)$. It is not too hard to check that these two expressions are equal.
A: Let's say we're talking about an elliptic curve $E$ over $\mathbb Q$.
Let $\alpha_p$ and $\beta_p$ be the Frobenius eigenvalues at a prime $p$ of good reduction (so $X^2 - a_p X + p = (X - \alpha_p)(X-\beta_p)$).
Then $$| E(\mathbb F_{p^2}) | = p^2 + 1 - \alpha_p^2 - \beta_p^2 = (1+p)^2 - (\alpha_p + \beta_p)^2 = (1 + p)^2 - a_p^2.$$ 
So you are asking if we can have $a_p = 0$ for all primes of good reduction.
The answer is no.

If $E$ has CM (as in your two examples), then $a_p = 0$ for a density $1/2$ set of primes.
If $E$ does not have CM, then $a_p = 0$ for a density $0$ set of primes.  (The precise distribution of the values of $a_p$ as $p$ varies is the subject 
of the Sato--Tate conjecture, which is now a theorem of many people.)
