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