Here are some hints:
Let $G$ be a group with a cyclic and odd group of automorphisms.
- Since $G/Z$ (Z being the center) is a subgroup of $\operatorname{Aut} G$, it will be cyclic. Deduce that $G = Z$, i.e. $G$ is abelian.
- Since $G$ is abelian, what can you say about $x\mapsto x^{-1}$ ? Deduce that $G \cong \bigoplus_{i} \mathbb Z/2\mathbb Z$, i.e. $G$ is an elementary abelian $2$-group.
- Now you know a lot about $G$, so you may try to find automorphisms of $G$ that will contradict that $\operatorname{Aut} G$ is cyclic.
I can give more hints if you tell where you're stuck.
-- editted: for step 3: For instance: If there are at least 3 factors involved in the direct product $G \cong \bigoplus_i (\mathbb Z/2\mathbb Z)$ then permuting these factors gives rise to an automorphism (for instance $(a,b,c,...)\mapsto (b,a,c,...)$). This implies $S_3$ appears as subgroup of the automorphism-group so it will surely not be cyclic. If there are $2$ factors $G\cong (\mathbb Z/2\mathbb Z)^2$ and it's easy to see that any permutation of the three involutions of this group is an automorphism.
I think there is a more beautiful way to derive the contradiction but I don't see it right now.
-- editted (much later): I just thought of the more beautiful way: If the direct sum has at least two terms, consider the automorphism that switches these terms $(a,b,c,\dots)\mapsto (b,a,c,\dots)$. This is an automorphism of order 2, a contradiction.
An important philosophy of group theory is to break up groups into their component pieces. This arises, for example, in extensions $H \to G \to G/H$ for normal subgroups $H$ of $G$, and motivates the search for simple groups. For the purposes of studying automorphisms, having a normal subgroup is good but not great (normal subgroups are fixed by inner automorphisms, but not outer ones, so you have to figure out how the outer ones can move the normal subgroup around).
Recall that a subgroup is characteristic if it is preserved by all automorphisms, not just the inner ones. Standard examples of characteristic subgroups include the center and the commutator subgroup. Suppose that $H < G$ is characteristic. Then one has a canonical homomorphism $\mathrm{Aut}(G) \to \mathrm{Aut}(H)$ given by restricting an automorphism of $G$ to its action just on $H$. The kernel of this homomorphism consists of those automorphisms of $G$ that fix $H$ pointwise. It follows that $|\mathrm{Aut}(G)| = \#\{$automorphisms of $G$ that fix $H$ pointwise$\} \times |$image of the homomorphism$|$. The latter factor necessarily divides $|\mathrm{Aut}(H)|$, as it is the size of a subgroup thereof.
Let $G = D_{2n}$ be a dihedral group of order $2n$, with $n\geq 3$. I claim that the subgroup $H = C_n$ of rotations is characteristic. Indeed, it is the unique proper subgroup containing an element of order $n$ (as all reflections have order $2$). Of course, $|\mathrm{Aut}(C_n)| = \phi(n)$ is Euler's totient function. When $n = 2^k$ for $k\geq 1$, $\phi(n) = 2^{k-1}$ counts the number of odd numbers less than $n$. This verifies your to-be-used statement that the automorphism group of a cyclic 2-group is a 2-group. It follows that the second factor in $|\mathrm{Aut}(G)|$ is a power of $2$ (since it is the size of a subgroup of a 2-group).
It remains to count the group of automorphisms of $D_{2n}$ that fix all rotations. There are various ways to do this count. The method that reduces to Babak Miraftab's answer is to observe that such an automorphism is determined by the image of a single reflection (as any one reflection, along with the rotations, generates the group), and that a given reflection can be sent to any other. Here is a less enlightening way to do the count. The group we care about is a subgroup of the symmetric group $S_4$ on the set of reflections. Since $|S_4| = 4! = 24$, it suffices to check that no automorphism has order $3$. The only permutations in $S_4$ of order $3$ cyclicly permute three things while leaving the last fixed. But the product of any two reflections is a rotation, and these we supposed are fixed; therefore the automorphisms we care about cannot fix a reflection without fixing all of them.
Best Answer
An automorphism of $C_n$ is uniquely determined by the image of $1$ (generator), and this has to be a generator, hence an invertible element. Hence we obtain a bijection $\mathrm{Aut}(C_n)\to (\mathbb{Z}/n\mathbb{Z})^{\times}$. Since we know that the multiplicative group of the integers modulo $n$ is cyclic for $n=p^k$ with $p>2$ prime (and other cases, see here), we have
$$ Aut(C_{p^k})\cong(\mathbb{Z}/p^k\mathbb{Z})^\times \cong \mathrm{C}_{p^{k-1}(p-1)} \cong \mathrm{C}_{\varphi(p^k)} .$$ In general we know when the automorphism group can be cyclic, see When is the automorphism group $\text{Aut }G$ cyclic?