This question has been explored thoroughly, and in more generality too. For general fields, I am aware of standard proofs. However, I was naively trying to prove it in the simple case of prime $p$ using elementary techniques, embarrassingly without much success. Most proofs use the non-trivial fact that for $d|p-1$, the polynomial $x^d-1$ has exactly $d$ solutions in the field $\mathbb{Z}/p\mathbb{Z}$ . Or a sufficiently relaxed fact: the polynomial $x^n-1$ has at most $n$ solutions in the field $\mathbb{Z}/p\mathbb{Z}$. You can check out the standard expositions here :http://www.math.uconn.edu/~kconrad/blurbs/grouptheory/cyclicmodp.pdf

Is there some proof that does not pull in fields and fundamental theorem of algebra here? I mean, the problem itself is simply one of modular arithmetic, and using fields, polynomial roots, fundamental theorem of abelian groups and such seems like an overkill.

I am being a bit fuzzy here, but does anybody have an elegant proof which uses only basic group theory and simple properties of primes? Or if not, can somebody give me some intuition as to why (relatively) deep results are required to prove such a tantalizingly simple statement?

  • $\begingroup$ Yes, use Fundamental Theorem of Finite Abelian Groups. proofwiki.org/wiki/… $\endgroup$ – SomeOne May 12 '16 at 17:56
  • 2
    $\begingroup$ There is seemingly a lot of irregularity to the least positive integer that serves as a primitive root as you vary the prime modulus. Because of this, there is almost certainly no hope of directly showing that the group is cyclic by producing a generator. If you're trying to prove that a group is cyclic, and you rule-out "produce a generator" as a possible approach, then you are pretty limited. I can't think that any alternative approach would be simpler than "show that the elements of order less than p-1 do not exhaust the group", and this approach amounts to the ones you describe. $\endgroup$ – Barry Smith May 12 '16 at 20:18
  • $\begingroup$ Maybe look at it from a number theoretic perspective, the fact that it is cyclic is equivalent to the existence of primitive roots for primes and looking at that might give you more insight into the nature of your problem and why (as far as i'm aware) there can't be a simpler proof than what you are aware of. $\endgroup$ – Uday Khanna Jun 21 '18 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.