4
$\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
    [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
    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