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?