Proving $2$ generates $(\mathbb{Z}/19\mathbb{Z})^*$ by only looking at a few powers So I'm first asked to compute, mod 19, the powers of 2, 
$$2^{2},2^{3},2^{6},2^{9}$$
which I compute as 
$$4,8,7,18$$
respectively.  
I'm then asked to prove that 2 generates $(\mathbb{Z}/19\mathbb{Z})^{*}$ based on the above.  I'm not seeing how you can only look at these powers to know that 2 generates the group.  Of course I could compute the rest of the powers of 2 and show that all $1\leq a\leq 18$ are congruent to $2^{k}$ for some integer $k$, but I get the impression that this is not what I'm supposed to be seeing here.
What I am noticing is that I've basically computed $2^{2}$ and $2^{3}$ and then a few combinations of them.  Trivially I can get $1$ as $2^{0}$ and 2 likewise, and I'm allowed to take negative integer powers so I must get $2^{-1}$.  If I somehow knew that $2^{-1}$ were not $4, 8, 7,$ or $18$ then that would be nice, but I don't see how I can be assured of that without explicit calculation--and I get the feeling this is supposed to be an exercise in not explicitly calculating these.
Maybe this is supposed to be "half calculation", like showing that because I can get $4\cdot 8=32$ and $4\cdot 7=28$ I must therefore be able to obtain ... I don't know what.  Any hints?  Or am I over-thinking this and I should just calculate every power of 2?
 A: By Fermat $\,2^{\large 18} \equiv 1,\,$ thus $\, 2\,$ has order $18\,$ iff $\,2^{\large 6}\!\not\equiv 1$ and $\,2^{\large 9}\!\not\equiv 1\,$ by the following
Order Test $\ \,a\,$ has order $\,n\iff \color{#0a0}{a^{\large n} \equiv 1}\,$ but $\,a^{\large n/p} \not\equiv 1\,$ for every prime $\,p\mid n.\,$
Proof $\ (\Leftarrow)\ $ By here $\,a\,$ has $\,\color{#c00}{{\rm order}\ k}\,$ dividing $\,\color{#0a0}n.\,$ If $\:k < n\,$ then $\,k\,$ is proper divisor of $\,n\,$ therefore $\,k\,$ arises by deleting at least one prime $\,p\,$ from the (unique) prime factorization of $\,n,\,$ hence $\,k\mid n/p,\,$ say $\, kj = n/p,\ $ so $\ a^{\large n/p} \equiv (\color{#c00}{a^{\large k}})^{\large j}\equiv \color{#c00}1^{\large j}\equiv 1,\,$ contra hypothesis. $\ (\Rightarrow)\ $ Clear, since by definition, $\, {\rm ord}(a) = n\,$ is the least exponent $\,k>0\,$ such that $\,a^k\equiv 1,\,$ so $\,a^{n/p}\not\equiv 1$.
A: If $2$ does not generate the whole order-18 group, it generates a proper subgroup of order dividing $18$, that is, of order $1$ or $2$ or $3$ or $6$ or $9$, which means that one of $2^1, 2^2, 2^3, 2^6, 2^9$ would be $\equiv 1$.
Um, actually ... it suffices to know that $2^9\not\equiv 1$ and $2^6\not\equiv 1$. Do you see why?
A: Here is an alternative proof based on knowing that $19\equiv3$ mod $4$ implies $n$ is a quadratic residue mod $19$ if and only if $-n$ is a quadratic non-residue (for $19\not\mid n$), which tells us, to begin with, that $2$ is a non-residue, since $-1\equiv18=2\cdot3^2$ mod $19$ is a non-residue.
There are $\phi(19)/2=9$ quadratic non-residues.  Of these, $\phi(\phi(19))=\phi(18)=6$ are generators of $(\mathbb{Z}/19\mathbb{Z})^*$.  Since $3\mid18$, no cube can be a generator, so $2^3=8$ and $(-4)^3\equiv-2^6=-64\equiv12$ are non-residues that cannot be generators.  Since the non-residue $-1$ is also clearly not a generator, the remaining $6$ non-residues must all be generators, and this includes $2$.
