1
$\begingroup$

Can you give me an example of generator of multiplicative group $$(\mathbb{Z}/p\mathbb{Z})^{*}=\{1, 2, \ldots, p-1\}.$$

Thanks.

  • 4
    1 for $p=2$ is an example.2011-11-06
  • 0
    Depends on what $p$ is.2011-11-06
  • 0
    @Zev Chonoles: is there exists clear formula for generator for any prime $p$?2011-11-06
  • 1
    Finding a generator for this group is computationally difficult in general.2011-11-06
  • 0
    @Aspirin: [No](http://en.wikipedia.org/wiki/Primitive_root_modulo_n#Finding_primitive_roots).2011-11-06
  • 0
    No. There is no clear formula.2011-11-06
  • 0
    @Bill Cook: and for $p=4k+1$? P.S. I want to proof that in such group exists element of order $4$.2011-11-06
  • 1
    @Aspirin: Why not make that your question...2011-11-06
  • 0
    @Aspirin, IIRC the multiplicative group is always cyclic. For an existence proof that should be enough.2011-11-06
  • 0
    @Zev Chonoles: because if generator there exists, than least statement will be obviously2011-11-06
  • 0
    @Henning Makholm: I'm very sorry but why this group is cyclic?2011-11-06
  • 0
    You are looking for primitive roots mod $p$. See Sloane's sequence A001918, http://oeis.org/A001918.2011-11-06
  • 0
    @Aspirin, it's a general fact about all finite fields that their multiplicative groups are cyclic. I don't remember a proof or reference, though, sorry.2011-11-06
  • 0
    @Henning Makholm: Am I right that multiplicative group of ahy field always cyclic?2011-11-06
  • 0
    @Aspirin: See this [question](http://math.stackexchange.com/questions/78416/a-question-about-the-proof-that-mathbbz-p-mathbbz-times-is-cyclic) for a proof that $(\mathbb{Z}/p\mathbb{Z})^\times$ is cyclic.2011-11-06
  • 0
    @Aspirin, last I checked it wasn't the case for $\mathbb Q$ or $\mathbb R$.2011-11-06
  • 0
    @Henning Makholm: Thanks a lot, a read it proof in book2011-11-06
  • 1
    http://en.wikipedia.org/wiki/Primitive_root_modulo_n2011-11-06
  • 0
    A slight generalization of that argument shows that any finite subgroup of the multiplicative group of a field is cyclic.2011-11-06
  • 0
    @Henning Makholm: *for finite field2011-11-06
  • 1
    You should make the title of your post a question or similar statement; as it is, your title is very uninformative.2011-11-06

1 Answers 1

3

I am putting together the question with the comments to figure out the real question. And, this is the answer.

As Henning said, the group is always cyclic. This is a special case of the fact that the multiplicative group of units from a finite field is always cyclic. In a cyclic group of order $n$, there is always an element of order $d$ for any $d$ that divides $n$.

The group $\mathbb{Z} / p \mathbb{Z}$ is order $p-1$. So, if $p = 4k+1$, as you mentioned in a comment, then this group is order $4k$. In that case, 4 divides the order of the group so there is guaranteed to be an element of order 4.

  • 0
    I wonder if finding an efficient algorithm for the generator would imply an efficient algorithm for the discrete logarithm problem? This is what comes to mind right away.2011-11-06
  • 2
    @pki, why would it? The cryptographic applications of discrete logarithms are usually for moduli where a generator is known and public already.2011-11-06