Number theory/combinatorial proof for cycliclity of $(\mathbb{Z}/p\mathbb{Z})^\times$

Question

I have tried everything I could and I think I'm conceding. I am trying to find a prove that $(\mathbb{Z}/p\mathbb{Z})^\times$ is cyclic without using FTFAG and theory of finite fields.

Does anyone have a nice combinatorial/number theory proof they know of?

Edit: I would even be satisfied with a linear algebra/analysis proof.

Answer 1

Of course, the group has order $\varphi (p)=p-1$. I would suggest consulting Gauß's Disquisitiones Arithmeticae (1801), where he is supposed to have given two proofs of the existence of primitive elements (one constructive). I believe this would do it, as you would then have an element of order $p-1$.