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.