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?

• $(\Bbb Z/19\Bbb Z)^{\ast}$ has order 18. To conclude $2$ is a generator, we need to eliminate $2,3,6$ and $9$ as possible orders, because, you know, Lagrange. – David Wheeler Mar 13 '15 at 18:38
• @DavidWheeler Actually, technically I don't know Lagrange. :) Well, I do, but I'm not supposed to. For now the class has only proved the special case for finite cyclic groups, that a number divides the order iff it is the order of a subgroup. Which makes me realize, actually, I can't use the fact that this group's subgroups must have order dividing 18 because I haven't proved its cyclic. Looks like I have more work to do. – Addem Mar 13 '15 at 18:52
• @David Actually you only need to eliminate maximal proper divisors of $18$ - see my answer. – Bill Dubuque Mar 13 '15 at 19:13
• @BillDubuque Indeed, that was pointed out by Hagen von Eitzen, who posted his answer as I was writing my comment. – David Wheeler Mar 13 '15 at 21:31
• @Aden Even in the absence of Lagrange, it should be clear that if $\langle a\rangle$ has $18$ elements, it generates $(\Bbb Z/19\Bbb Z)^{\ast}$, and if it has lesser order, it does not. One does not need Lagrange to show that $a^k = e \implies o(a)|k$, the division algorithm will suffice. – David Wheeler Mar 13 '15 at 21:45

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?

• Yep, that makes sense. – Addem Mar 13 '15 at 18:41

By Fermat $\,2^{18} \equiv 1,\,$ thus $\, 2\,$ has order $18\,$ iff $\,2^6\not\equiv 1\,$ and $\,2^9\not\equiv 1\,$ by the following

Order Test $\ \,a\,$ has order $\,n\iff a^n \equiv 1\,$ but $\,a^{n/p} \not\equiv 1\,$ for every prime $\,p\mid n.\,$

Proof $\ (\Leftarrow)\$ If $\,a\,$ has $\,\color{#c00}{{\rm order}\ k}\,$ then $\,k\mid n\,$ (proof). If $\:k < n\,$ then $\,k\,$ is proper divisor of $\,n\,$ therefore $\,k\,$ arises by deleting at least one prime $\,p\,$ from the prime factorization of $\,n,\,$ hence $\,k\mid n/p,\,$ say $\, kj = n/p,\$ so $\ a^{n/p} \equiv (\color{#c00}{a^k})^j\equiv \color{#c00}1^j\equiv 1,\,$ contra hypothesis. $\ (\Rightarrow)\$ Clear.

• Interesting answer, but the order test you use talks about every prime divisor of $n$. However, in your example, you use non-prime divisors 6 and 9. Am I misunderstanding something? – Addem Mar 13 '15 at 19:00
• $18$ has prime divisors $\,p = 2,3\,$ so the test is that $\,a^{18/p}\not\equiv 1\,$ for $\, p = 2, 3.\$ The test is very useful and should be well-known by every student of number theory and group theory. – Bill Dubuque Mar 13 '15 at 19:04
• Bill is talking about maximal divisors, here-which for any positive integer $n$ are of the form $n/p$ for some prime $p$ that divides $n$. In the case of $18 = 2\cdot 3^2$, the only primes that divide $18$ are $2,3$, so all we need to test is $6 = 18/3$ and $9 = 18/2$. If we were talking about $30$, the maximal divisors would be $6,10,15$. – David Wheeler Mar 13 '15 at 21:36

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$.

• Yes, from the Order Test (see my answer) we know that $\,a\,$ is a generator $\iff a^9\not\equiv 1\,$ and $\,a^6\not\equiv 1,\,$ i.e. $\,a\,$ is not a square nor a cube. – Bill Dubuque Jan 22 '17 at 18:48