How can I test if an element g is a generator of a group G with a known number of elements, N?

Question

Let's say $G$ has $1000$ elements. Without looping through each $g^m$, how can I show that $g$ is a generator? I've deduced that I must prove that the order of $g = N$, or in this case $1000$, but I'm not sure how to go about that. Any help is appreciated. Thanks!

Answer 1

If the prime factors of $|G| = N$ are known, then one can test $g^m \neq e$ (where $e$ means the identity element of the group $G$) for a relatively small subset of the possible exponents. Namely, one want to show that $g^m \neq e$ for each $m = N/p$ where $p$ runs through the prime divisors of $N$.

Note that we automatically know $g^N = e$. So the goal is to prove that no proper divisor $D$ of $N$ will also serve to achieve $g^D = e$. This conclusion follows from what we would show above, for if $D$ were a proper divisor of $N$, then some prime divisor of $N$ has more repeated factors in $N$ than in $D$. Let $p$ be such a prime divisor of $N$. According to the above criterion, $D$ divides $N/p$. But if $g^{N/p} \neq e$, it cannot be the case that $g^D = e$ (because $D$ divides $N/p$).

Answer 2

The general theory has been given in another answer but IMHO this is one of those results where a specific example makes the theory very much easier to understand.

So, suppose you have an element $g$ of a group $G$, where $|G|=1000$. You want to know whether or not $g$ has order $1000$.

First of all, you know that the order of $g$ is a factor of $|G|$, and so the possible values for the order are $$1000,\,500,\,250,\,200,\,125,\,100,\,50,\,40,\,25,\,20,\,10,\,8,\,5,\,4,\,2,\,1\,.$$ We want to rule out the possibilities $$500,\,250,\,200,\,125,\,100,\,50,\,40,\,25,\,20,\,10,\,8,\,5,\,4,\,2,\,1\,.$$ So, suppose that we have checked that $500$ doesn't work, that is, we have checked $g^{500}\ne e$. (We can think later about how to do this efficiently, for now let's just say we've done it.) The point is that we now do not need to check that $g^{250}\ne e$; for if $g^{250}$ were to equal $e$ then we would have $g^{500}=e^2=e$; and we have already checked that this is not true. In the same way, we don't need to check $125,100,50,25,20,10,5,4,2,1$ which leaves us with $$200,\,40,\,8\,.$$ So, check that $g^{200}\ne e$; then for the same reasons as above, we don't need to check $40$ or $8$.

So what it comes down to is: $g$ is a generator of $G$ if and only if $$g^{500}\ne e\quad\hbox{and}\quad g^{200}\ne e\ .$$ If you think carefully you should see how this gives the general rule as stated in other answers: $g$ is a generator of a group of $n$ elements if for every prime factor $p$ of $n$ we have $g^{n/p}\ne e$.

Doing the problem the "obvious" way, we would have $999$ things to check: as it is, only two!

You can do the necessary computations by repeated squaring and related techniques: in this case you could successively compute $$\eqalign{g^2&=(g)(g)\cr g^4&=(g^2)^2\cr g^5&=(g^4)g\cr g^{10}&=(g^5)^2\cr g^{20}&=(g^{10})^2\cr g^{40}&=(g^{20})^2\cr g^{50}&=(g^{40})g^{10}\cr g^{100}&=(g^{50})^2\cr g^{200}&=(g^{100})^2\cr g^{400}&=(g^{200})^2\cr g^{500}&=(g^{400})g^{100}\ ,\cr}$$ a total of just $11$ calculations to show that $g$ is a generator.