Aut(G) = $C_3$, G = ? Is there a group G such that Aut(G) = $C_3$?  What if we replace 3 with a prime number p?
 A: The original question has already been answered, but Jared Weinstein asked in a comment about what happens if we don't assume the axiom of choice.  I've convinced myself that it's consistent with ZF to have a vector space over $\mathbb{F}_2$ with automorphism group $C_3$.  In case any set theorists (other than me) are looking at this question, here's the model I have in mind.  (It's a permutation model, using atoms, but the Jech-Sochor theorem suffices to convert it into a ZF-model.)  Start with the full universe $V$  built from a countable set $A$ of atoms (and satisfying AC).  In $V$, give $A$ the structure of a $\mathbb{F}_4$-vector space, obviously of dimension $\aleph_0$.  (The relevance of the 4-element field $\mathbb{F}_4$ is that the two elements that are not in the 2-element subfield are cube roots of 1, so multiplication by either of them gives an automorphism of order 3.)  Let $G$ be the group of automorphisms of this vector space, and let $M$ be the Fraenkel-Mostowski-Specker permutation submodel of $V$ determined by the group $G$ with finite subsets of $A$ as supports.  In $M$, $A$ is an  $\mathbb{F}_4$-vector-space.  Multiplication by the elements of $\mathbb{F}_4\setminus\mathbb{F}_2$ gives a $C_3$-action on the underlying abelian group.  Fairly easy calculations (admittedly not yet written down) convince me that this abelian group has no automorphisms in $M$ beyond this copy of $C_3$.  
A: There is no group $G$ (finite or infinite) for which $Aut(G) \cong C_p$ (the cyclic group of order $p$), if $p > 1$ is an odd number. 
Suppose otherwise. The inner automorphism group $Inn(G)$ is a subgroup, also cyclic, and a well-known exercise in group theory is that if $Inn(G) \cong G/Z(G)$ is cyclic, then $G$ is abelian. 
An abelian group $G$ has an involution given by inversion. Unless inversion is trivial, we get an element of order 2 in $Aut(G) = C_p$, contradiction. 
If inversion is trivial, then the abelian group $G$ becomes a vector space over $\mathbb{F}_2$. In that case it is an easy to prove that either $Aut(G)$ is trivial or has an element of order 2; either way we get a contradiction. 
Edit: After listening to some comments about this at meta, I amended my answer so that it gives less away or leaves a bit more to the imagination, or so I hope. 
