I know that this follows from the existence and non-degeneracy of the Weil pairing. A consequence of the existence of the Weil pairing is that, if the whole $n$-torsion is defined over $\mathbf Q$, then the $n$-th roots of unity $\mu_n \subseteq \mathbf Q$. This of course implies $n=2$. Thus, for an odd prime $p$, $E(\mathbf Q)[p]$ is cyclic, being a proper subgroup of $\mathbf Z/p \times \mathbf Z/p$. Putting this information together for the various primes dividing $n$ shows that for a general odd $n$, $E(\mathbf Q)[n]$ is cyclic.
But this seems to me like over-kill. Could this simple fact be proven without using the Weil pairing?