# Proof of $\operatorname{Aut}(C_p)\cong C_{p-1}$ by means of permutations?

This is a different approach than this other of mine, but to the same task: try to prove the result without explicitly mention fields (see e.g. here). In the spirit, I think this is similar to this other question.

Let $$p$$ be a prime and $$C_p=\{e,a,\dots,a^{p-1}\}$$ the cyclic group of order $$p$$. Every automorphism of $$C_p$$ permutes the nontrivial elements of $$C_p$$, namely $$\varphi\in\operatorname{Aut}(C_p)\Longrightarrow\exists\tau\in S_{p-1}$$ such that $$\varphi(a^i)=a^{\tau(i)}, i=1,\dots,p-1$$. I assume as already known $$\left|\operatorname{Aut}(C_p)\right|=p-1$$. Now I'm trying to prove $$\operatorname{Aut}(C_p)\cong C_{p-1}$$ by showing that there is a $$(p-1)$$-cycle $$\sigma\in S_{p-1}$$ such that, if $$\varphi\colon G\to G$$ is defined by $$\varphi(e)=e$$ and $$\varphi(a^i)=a^{\sigma(i)}$$ for $$i=1,\dots,p-1$$, then $$\varphi\in\operatorname{Aut}(C_p)$$. My idea was to deploy some low-$$p$$ case, in order to reveal a "pattern", suitable for a guessed generalization to every $$p$$ (to be later proven by a lemma). For $$p=5$$ and $$p=7$$, as suitable $$\sigma$$'s I've come up to the following ones:

• $$p=5$$: $$\sigma=(1342)$$, ​$$\sigma=(1243)$$;
• $$p=7$$: $$\sigma=(154623)$$, ​$$\sigma=(132645)$$,

namely: for all the above $$\sigma$$'s, the map $$\varphi(e)=e$$, $$\varphi(a^i)=a^{\sigma(i)}$$ is an automorphism of $$C_5$$ or $$C_7$$, and $$|\varphi|=4$$ or $$|\varphi|=6$$ (so $$\operatorname{Aut}(C_5)\cong C_4$$ and $$\operatorname{Aut}(C_7)\cong C_6$$ are proved).

Differently from my hope, none of the four pairs $$(\sigma_{p=5},\sigma_{p=7})$$ gives me any hint for a guessed generalization for a $$\sigma$$ valid for every $$p$$. Am I wrong in expecting such an approach to succeed, or is there indeed such a sought $$\sigma=\sigma(p)$$?

Edit. In principle, it is not necessary to explicitly show such a $$(p-1)$$-cycle; it's enough to prove its existence. And it exists if and only if the system of $$\frac{(p-1)^2-(p-1)}{2}+p-1-\frac{p-1}{2}=\frac{1}{2}(p-1)^2$$ linear congruences modulo $$p$$ in the $$p-1$$ unknowns $$\sigma(1),\dots,\sigma(p-1)$$, arising from imposing the operation-preserving condition, has a solution which is a $$(p-1)$$-cycle. Maybe this is always the case?

Edit#2. Seemingly, the system mentioned in the previous Edit has solutions: \begin{alignat}{3} &\sigma(1) &&= (p-1)c &&&\pmod p \\ &\sigma(2) &&= (p-2)c &&&\pmod p \\ &\dots \\ &\sigma(p-2) &&= 2c &&&\pmod p \\ &\sigma(p-1) &&= c &&&\pmod p \\ \tag 1 \end{alignat} where $$c$$ is a parameter. So, we'd be left to prove that, for every $$p$$, there is a value of $$c$$ such that $$(1)$$ is a cycle. Perhaps this is easy(?), but even if so, we'd firstly need to prove $$(1)$$, which is just an educated guess based on the worked out $$p=5,7,11$$ cases.

Edit#3. As pointed out in the comments, this approach turns into the problem of proving that there is a primitive root modulo $$p$$ for any prime $$p$$. In fact (modulo the fact that $$(1)$$ is still just an educated guess...), $$(1)$$ is a cycle if and only if, set $$l:=p-c$$ (with then $$2\le l\le p-2$$), $$l$$ is such that: $$l^k\not\equiv 1\pmod p$$ for every $$k=1,\dots,p-2$$, i.e. if and only if $$l$$ is a primitive root modulo $$p$$ (which in turn is equivalent to $$\Bbb Z_p^\times$$ being cyclic). So, the only we can say is that, if $$l$$ is a primitive root modulo $$p$$, then the cycle which does the trick is: $$\sigma=(1,\space l,\space l^2\pmod p,\space\dots,\space l^{p-2}\pmod p)$$ Therefore, the ciclicity of $$\operatorname{Aut}(C_p)$$ can't be gotten independently from the ciclicity of $$\Bbb Z_p^\times$$, or at least not by the way argued here.

• I think this approach would work, but you've assumed the size of the automorphism group is $p-1$, which is one of the nontrivial parts of the problem. Oct 28, 2021 at 15:40
• Basically, you want a primitive root modulo $p$. Suppose a generator $\tau$ sends $a$ to $a^r$. Then $\tau^2(a) = a^{r^2}$, $\tau^k(a)=a^{r^k}$, and so you want $r$ to have multiplicative order $p-1$ modulo $p$. Conversely, if $r$ is a primitive root, then the cycle given by $(1,r,r^2\bmod p, r^3\bmod p,\ldots, r^{p-2}\bmod p)$ is the permutation in question. Note in your examples that $3$ is a primitive root modulo $5$, and $5$ is a primitive root modulo $7$. But the question of finding a primitive root modulo $p$ for arbitrary $p$ is somewhat complex... Oct 28, 2021 at 15:46
• But in any case, this turns into a problem of proving that there is a primitive root modulo $p$ for any prime $p$... which is essentially proving that the multiplicative group modulo $p$ is cyclic... which is essentially proving that the automorphism group is cyclic. As far as I know, there is no known "method" to find a primitive root modulo $p$, so I'm not sure if you are going to see a "pattern" developing here. Oct 28, 2021 at 15:48
• I think that there are $p-1$ automorphisms is not hard. If $C_p=\langle x\rangle$, then it suffices to know the image of $x$, whence there are at most $p$ endomorphisms. But the map $x\mapsto x^i$ is a homomorphism simply because $(x^ax^b)^i=x^{ai}x^{bi}$. Thus there are $p$ endomorphisms, and one is the zero map. This gives $p-1$ automorphisms, but says nothing about their orders. Oct 28, 2021 at 15:50
• – Eric
Nov 1, 2021 at 14:34