So I'm first asked to compute, mod 19, the powers of 2,


which I compute as



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?

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

4 Answers 4


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?

  • $\begingroup$ Yep, that makes sense. $\endgroup$
    – Addem
    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$

  • $\begingroup$ 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? $\endgroup$
    – Addem
    Mar 13, 2015 at 19:00
  • 2
    $\begingroup$ $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. $\endgroup$ Mar 13, 2015 at 19:04
  • $\begingroup$ 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$. $\endgroup$ 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$.

  • $\begingroup$ 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. $\endgroup$ 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 = [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\}$)


$\; [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}$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .