3
$\begingroup$

Let us say I have to find all the generators for modulo $p=7$. That must mean that:

$$\mathbb{Z}_7 = \mathbb{Z}^*_7 = \{1,2,...,7-1\}$$

So now I need to get all the generators for $7$. Now I choose randomly from the group $\mathbb{Z}_7$ and pick the number $3$. So if $3^n$ for $n = \{1,2,\dotsc,7-1\}$ can generate all elements from $\mathbb{Z}_7$, the number is considered a generator.

$$3^1 \pmod 7\equiv 3\\ 3^2 \pmod 7\equiv 2\\ 3^3 \pmod 7\equiv 6\\ 3^4 \pmod 7\equiv 4\\ 3^5 \pmod 7\equiv 5\\ 3^6 \pmod 7\equiv 1$$

Now I have found one generator. Someone claimed one can find all generators in the group with a faster method, when one already has one generator. Can someone please show me how that works?

$\endgroup$
  • 5
    $\begingroup$ How can $\Bbb Z_7$ be the same as $\Bbb Z_7^*$? $\endgroup$ – Bernard Apr 1 at 21:32
  • $\begingroup$ Hi and welcome! Your question is not really clear. Are you finding a method to discover all the generator of $\mathbb Z_7^*$ having found a generator of this group? $\endgroup$ – Menezio Apr 1 at 21:36
  • $\begingroup$ @Bernard hi, I always thought they were the same? Aren't they the same? $\endgroup$ – Heinrich Jensen Apr 1 at 21:42
  • 1
    $\begingroup$ @Menezio hi, I'm just trying to find all the generators in the cyclic group as fast as possible. I've read a lot of different things online, but I would just love when someone could go through my example and explain how they find the generators. The fastest method I have found is when you find a generator and then, so it is claimed online, it is easy to find all the other elements. KR $\endgroup$ – Heinrich Jensen Apr 1 at 21:44
  • $\begingroup$ No: the first is the field with $7$ elements, the other is its set of units (non-zero elements). Only the latter is a multiplicative group, and it has order $6$. $\endgroup$ – Bernard Apr 1 at 21:45
6
$\begingroup$

We know that $\mathbb Z_7^*$ is a group with multiplication, and it is cyclic with generator the element $3$ as you show. To find the other generators you can do this: since $\mathbb Z_7$ has got six elements and it is cyclic, then it's isomorphic to $\mathbb Z_6$ and the isomorphism is the following (try to show this as exercise): \begin{equation} \varphi:(\mathbb Z_6,+) \longrightarrow (\mathbb Z_7^*, \cdot), \quad i\longmapsto 3^i \end{equation} Now, since $\varphi$ is an isomorphism, it maps generators in generators (and vice-versa). The generators of $\mathbb Z_6$ are just $1$ and $5$ (numbers coprime with $6$ smaller than $6$), so the generators of $\mathbb Z_7^*$ are $\varphi(1)=3^1=3$ and $\varphi(5)=3^5=5$ modulo $7$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thank you so much! Now I understand it! Last question: it is the correct way I find the first generator (the three) which you use to calculate 3 and 5? Or is there a faster method? $\endgroup$ – Heinrich Jensen Apr 1 at 21:58
  • 1
    $\begingroup$ I don't know a general method to find the first generator, so it is ok what you have done $\endgroup$ – Menezio Apr 1 at 22:04
8
$\begingroup$

Here it is: in a cyclic group of order $n$, with generator $a$, all subgroups are cyclic, generated (by definition) by some $a^k$, and the order of $a^k$ is equal to $$\frac n{\gcd(n,k)}.$$ Therefore $a^k$ is another generator of the group if and only if $k$ is coprime to $n$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Hi, thanks. So I find the co-primes to three that are elements of the cyclic group? Which in this case would be 2, 4, 5? And then I say 7/gcd(7,2), 7/gcd(7,4) and 7/gcd(7,5)? And the result(s) will be the other generators? $\endgroup$ – Heinrich Jensen Apr 1 at 21:53
  • 1
    $\begingroup$ No quite: the exponents which are coprime to $6$. This makes much less. Further, it is very long to check, you indeed obtain generators. $\endgroup$ – Bernard Apr 1 at 21:58

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.