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?

  • 2
    $\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$ – David Wheeler Mar 13 '15 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 '15 at 18:52
  • $\begingroup$ @David Actually you only need to eliminate maximal proper divisors of $18$ - see my answer. $\endgroup$ – Bill Dubuque Mar 13 '15 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$ – David Wheeler Mar 13 '15 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$ – 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?

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

  • $\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 '15 at 19:00
  • 1
    $\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$ – Bill Dubuque Mar 13 '15 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$ – 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$.

  • $\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$ – Bill Dubuque Jan 22 '17 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.