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

Question

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?

Answer 1

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?

Answer 2

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$

Answer 3

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

Answer 4

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 = [1]_{19}$ ($[1]_{19}$ is the identity).

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

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

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

But

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