Prove that for $n\gt 2$, $| \operatorname{Aut}(D_n)|\le n\,\phi(n)$ where $D_n$ is the dihedral group with $2n$ elements and $\phi$ is Euler phi function.
Let $\rho$ be a rotation such that $o(\rho)=n$, that is $R_n = \langle\rho\rangle$, and $\psi$ an automorphism of $D_n$; then $\psi(\rho)$ must have order $n$ and there are only $\phi(n)$ such elements in $D_n$ and they are all rotations, therefore $\psi(R_n)=R_n$. Now let $\iota$ be the reflection through the $x$-axis, we have to send it in one of the $n$ reflection and since $D_n = \langle\rho, \iota \rangle$, $\psi$ is univocally determined.
In conclusion we have at most $n\phi(n)$ choices for $\psi$.
I could have also considered all the sets with two elements that generate $D_n$ which are of the form $\{\rho, \iota\}$ with $\rho$ a rotation of order $n$ and $\iota$ a reflection (there are $n\phi(n)$ of them); since an automorphism sends a set of generators into a set of generators we have again at most $n\phi(n)$ automorphisms (a rotation will be sent in a rotation) obtained by extending to a homomorphism the various choices (which give us bijective functions). Moreover there are exactly $n\phi(n)$ of them because every choice give us a different automorphism.
Are both solutions, and my remark, correct?
Thanks in advance
Edit: I was wrong saying that the only sets of two elements generating $D_n$ are of the form $\{\rho, \iota\}$, because there are also sets formed by two reflections, but since a rotation must be sent in a rotation my second proof should be correct.
Best Answer
Your explanation is correct. I have a remark that the inequality you want to prove is indeed an equality.
Let $C_n$ denote the cyclic group of order $n$. The group $G:=\text{Aut}\left(D_n\right)$ is isomorphic to the semidirect product $H:=C_n\rtimes \text{Aut}\left(C_n\right)$, where $$\left(c_1,f_1\right)\cdot \left(c_2,f_2\right):=\big(c_1\,f_1\left(c_2\right),f_1\circ f_2\big)$$ for all $c_1,c_2\in C_n$ and $f_1,f_2\in\text{Aut}\left(C_n\right)$. If $C_n$ is generated by $c$, then each element of $\text{Aut}\left(C_n\right)$ sends $c$ to $c^k$ for some $k=1,2,\ldots,n$ with $\gcd(k,n)=1$, and we write $\gamma_k$ for this element of $\text{Aut}\left(C_n\right)$.
The reason that $G$ is isomorphic to $H$ is as follows. Let $$D_n=\left\langle r,s \,|\,r^n=s^2=1\text{ and }rs=sr^{-1}\right\rangle=\left\{1,r,r^2,\ldots,r^{n-1},s,rs,r^2s,\ldots,r^{n-1}s\right\}\,.$$ Hence, for each $\tau\in G$, it suffices to look at $r_\tau:=\tau(r)$ and $s_\tau:=\tau(s)$. We have $r_\tau=r^{k}$ and $s_\tau=r^{j}s$ for some $k=1,2,\ldots,n$ with $\gcd(k,n)=1$ and for any $j=0,1,2,\ldots,n-1$. Thus, we write $\tau_{j,k}$ for this automorphism $\tau$. Then, the map $\psi:G\to H$ sending $\tau_{j,k}$ to $\left(c^j,\gamma_k\right)$ is a group isomorphism. That is, $$\big|\text{Aut}\left(D_n\right)\big|=|G|=|H|=\left|C_n\right|\,\big|\text{Aut}\left(C_n\right)\big|=n\,\phi(n)\,.$$ You have to fill in a lot of gaps I intentionally left out, of course.
P.S. Interestingly, the condition $n>2$ is important. It turns out that $D_2\cong C_2\times C_2$ is extraordinary. That is, $$\text{Aut}\left(D_2\right)\cong\text{Aut}\left(C_2\times C_2\right)\cong \text{GL}_2\left(\mathbb{F}_2\right)\cong S_3\,,$$ where $S_3$ is the symmetric group on $3$ symbols.