# Efficiently prove $2$ generates $(\mathbb{Z}/19\mathbb{Z})^*$ [Order Testing]

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. Mar 13, 2015 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. Mar 13, 2015 at 18:52
• @David Actually you only need to eliminate maximal proper divisors of $18$ - see my answer. Mar 13, 2015 at 19:13
• @BillDubuque Indeed, that was pointed out by Hagen von Eitzen, who posted his answer as I was writing my comment. Mar 13, 2015 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. Mar 13, 2015 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. Mar 13, 2015 at 18:41

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

Another handy order test is the converse below, with $$\,o(a) :=$$ order of $$\,a$$.

$$\rm\color{#0a0}{Coprime}$$ Order Test $$\ o(a)\!=\!p\!=\!{p_1\cdots p_k} \Rightarrow o(a^{p/p_i}) = p_i\,$$ & conversely for pair $$\rm\color{#0a0}{coprime}$$ $$\,p_i$$

Proof $$\ (\Rightarrow)\ \ (a^{p/p_i})^n\equiv 1\Rightarrow o(a)=p\mid (p/p_i)n\Rightarrow p_i\mid n,\,$$ and $$\,(a^{p/p_i})^{p_i}\equiv a^p\equiv 1$$.

$$\ (\Leftarrow)\,\ a^n\equiv 1\Rightarrow\,(a^{p/p_i})^n\equiv 1\Rightarrow o(a^{p/p_i})\!=\!p_i\mid n,\,$$ thus $$\,p=p_1\cdots p_k\mid n\,$$ by $$\,p_i\,$$ pair $$\rm\color{#0a0}{coprime}$$, and $$\,a^p \equiv (a^{p/p_i})^{p_i}\equiv 1^{p_i}\equiv 1$$

• 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? Mar 13, 2015 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. Mar 13, 2015 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$. Mar 13, 2015 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. Jan 22, 2017 at 18:48

Rather than employing elementary group theory, we can solve this using three elementary propositions in monoid theory:

Let $$\mathcal M$$ be a monoid with identity element $$e$$ and with a finite carrier set.

Proposition 1: An element $$a \in \mathcal M$$ is invertible if and only if there exists a positive integer $$m$$ satisfying $$a^m = e$$. Moreover, if $$m$$ is the minimal such integer, then the set $$\text{<}a\text{>} = \{ a^j \mid 1 \le j \le m\}$$ forms a cyclic group with $$m$$ distinct elements.

Proposition 2: If for $$a \in \mathcal M$$ where $$a \ne e$$ there exists a positive integer $$m$$ satisfying

$$(a^m)^2 = e$$

then $$a$$ is invertible and $$\text{<}a\text{>}$$ contains an even number of elements. Moreover, if $$m$$ is the minimal such integer, then the set $$\text{<}a\text{>} = \{ a^j \mid 1 \le j \le 2m\}$$ forms a cyclic group with $$2m$$ distinct elements.

Proposition 3: If for $$a \in \mathcal M$$ where $$a \ne e$$ there exists a positive integer $$m$$ such that

$$e \notin \{ a^j \mid 1 \le j \le m\} \, \land \, a^{2m} = e$$

then the set $$\text{<}a\text{>} = \{ a^j \mid 1 \le j \le 2m\}$$ forms a cyclic group with $$2m$$ distinct elements.

Consider the $$\text{mod-}19$$ residue classes under multiplication; it forms a monoid. Moreover, it contains $$19$$ elements and the blocks can be represented as follows:

$$\Bbb Z/19\Bbb Z = \{ \,[k]_{19} \mid -9 \le k \le 9 \}$$

Observe that $${[-1]_{19}}^2 = _{19}$$ ($$_{19}$$ is the identity).

Since $${[2^9 ]_{19}} = [-1]_{19}$$, all that is needed to show that $$\text{<}_{19}\text{>} = \{ {[2^j]_{19}} \mid 1 \le j \le 18\}$$ is cyclic with $$18$$ elements is to check that

$$\; [2^4]_{19} \ne _{19}$$
$$\; [2^5]_{19} \ne _{19}$$
$$\; [2^7]_{19} \ne _{19}$$
$$\; [2^8]_{19} \ne _{19}$$

(the OP has already calculated $$\{2,4,8,7,-1\}$$)

But

$$\; [2^4 ]_{19} \ne _{19} \text{ iff } [2^6]_{19} \ne [2^2]_{19}$$
$$\; [2^5 ]_{19} \ne _{19} \text{ iff } [2^6 ]_{19} \ne [2^1]_{19}$$
$$\; [2^7 ]_{19} \ne _{19} \text{ iff } [2^9]_{19} \ne [2^2]_{19}$$
$$\; [2^8 ]_{19} \ne _{19} \text{ iff } [2^9 ]_{19} \ne [2^1]_{19}$$