3
$\begingroup$

Find the smallest generator for a group $\mathbb{Z}^{*}_{31}.$

It is not said, but I assume that it is about multiplication, because addition would be a trivial one (1 would be a generator).

  • 0
    We use $^*$ or $^\times$ superscripts to refer to the multiplicative group of units. See [this wikipedia page](http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n), especially the section on generators.2012-02-23
  • 0
    @williamdemeo: But isn't it that * sign here denotes that this is a group without the $\{0\}$ element?2012-02-23
  • 0
    Maybe. How does your book define it?2012-02-23
  • 0
    @williamdemeo: It is said that it is all about the $\{0\}$ element. None symbol denotes whether it is multiplication or addition. It is always said directly (except this one).2012-02-23
  • 0
    I suspect they mean the multiplicative group $(\mathbb Z/31\mathbb Z)^{\times}$, in which case the generating set (and your answer) is given in the table at the bottom of the page I mentioned, but I could be wrong. Of course, you should know how to find the smallest generator, or "primitive root" (without refering to this table). Think about it, and if you are still unsure I'll try to post an answer...2012-02-23
  • 0
    [This wikipedia page](http://en.wikipedia.org/wiki/Primitive_root_modulo_n#Finding_primitive_roots) explains how to compute the primitive roots, and points out that there is no known general formula, so you just have to compute!2012-02-23

1 Answers 1

5

The $*$ in $\mathbb{Z}^{*}_{31}$ means that you are indeed dealing with the multiplicative group.

I have a feeling you are expected to just compute. Luckily, the computation is relatively short. Start with $2$. Since $2^5\equiv 1\pmod{31}$ (you may be using different notation), $2$ is not a generator: it has order $5$, not $30$.

So now try $3$. If $3$ is not a generator, then the powers of $3$ generate a proper subgroup of our group. Our group has $30$ elements, so the proper subgroups have size $1$, $2$, $3$, $5$, $6$, $10$, or $15$. So we do not need to compute too many powers modulo $31$.

If we find out that $3^{15}\not \equiv 1\pmod{31}$, that will also rule out $1$, $3$, and $5$. We must also rule out $6$ and $10$.

First we rule out $6$. Note that $3^3\equiv -4\pmod{31}$. So $3^6\equiv 16\pmod{31}$. Thus $3^9\equiv -64\equiv -2\pmod{31}$, and therefore $3^{10}\not\equiv 1\pmod{31}$. That rules out $10$. Since this is homework, I will leave it to you to rule out $15$. With a calculator, it is particularly easy, since one need not be afraid of largish numbers.

We end up finding that $3$ is a generator. Since $2$ isn't, $3$ is the smallest one.

Remark: We could just have computed the powers of $3$, reducing modulo $31$. Here is a start: $3, 9, 27, 19, 26, 16, 17, 20, 29, 25, 13, 8, 24, 10, 30$. Now it's all over, because we have computed $15$ powers and not reached the identity. Much more efficient (at least for $31$) than the argument of the main post, which used more in the way of group-theoretic ideas. However, with substantially larger numbers, the proper approach is a combination of ideas and brute force. By the way, finding a generator, for huge primes, has practical applications.

  • 0
    Nice explanation +12012-02-23
  • 0
    @André Nicolas: Nice, thanks. Only one question. Why we can assume, that "If 3 is not a generator, then the powers of 3 generate a proper subgroup of our group."?2012-02-23
  • 0
    In any finite group, the powers of any element $a$ form a subgroup of $G$. Quick reminder of proof: Look at $a$, $a^2$, $a^3$, and so on. Since $G$ is finite, these are not all distinct. Suppose $m and $a^n=a^m$. Then $a^{n-m}$ is the identity, and $a^{n-m-1}$ is the inverse of $a$. So inverse of any power of $a$ is a power of $a$. End. In our case, **proper** subgroup because if it is full group, $3$ is generator. We wanted to rule out all ways $3$ can fail to be generator. We could just have computed all the powers, seen there are $30$.2012-02-23
  • 0
    @teodore: I have added a remark that gives a "trivial" way to do the job. The reason I avoided it in the main post is that problems like this are a good way to learn about some important group-theoretic ideas, so I did not want to write out a completely "no-thinking" solution.2012-02-23
  • 0
    @AndréNicolas: Thanks a lot. The last thing. Why we can only focus on $30$ divisors (so $k = 1,2,3,5,6,10$ or $15$) while checking whether $3^k \not\equiv 1 \pmod{31}$? Why we don't need to check for example if $ \ 3^7 \not\equiv 1 \pmod{31}$?2012-02-23
  • 0
    By Lagrange's Theorem, the order of the subgroup generated by $a$ **divides** the order of the full group. The end. Or, if you are familiar with elementary number theory but not yet group theory, the order of an element divides $p-1$. Standard proof: Let $k$ be the smallest positive integer such that $a^k \equiv 1 \pmod p$. If $k$ does not divide $p-1$, then $p-1=kq+r$ where $0. But then fairly easily $a^r\equiv 1\pmod{p}$, contradicting choice of $k$ as smallest. Lagrange is better, since you are taking group theory, so should develop a group viewpoint.2012-02-23