I am working on a project in my group theory class to find an outer automorphism of $S_6$, which has already been addressed at length on this site and others. I have a prescription for how to go about finding this guy, but I have a larger conceptual question – what does an outer automorphism really look like? Is there an intuitive way to understand the difference between an inner and an outer automorphism? Inner automorphisms have always seemed easier for me to understand since we have an explicit representation $ghg^{-1}$ for members of the group. I can also understand this representation in terms of the Rubik's cube – rotate an edge, rotate a perpendicular edge, and the rotate the other edge back (is not the same as just rotating the perpendicular edge). What does an "outer automorphism" look like?
[Math] What does an outer automorphism look like
abstract-algebragroup-actionsgroup-theoryintuitionsymmetric-groups
Related Solutions
I think of the outer automorphism group $$\operatorname{Out}(G):=\frac{\operatorname{Aut}(G)}{\operatorname{Inn}(G)}$$ as being "all automorphisms, apart from the obvious ones we always get". So removing the "obvious" inner ones, which in many ways look like the group itself, allows us to study the "true" symmetries of the group.
Therefore, outer automorphisms are not automorphisms, but are equivalence classes of automorphisms. This is extremely similar to viewing elements of groups as words over the generators - elements are not words, but are equivalence classes of words.
For example, consider the free group on two generators, $F(a, b)$. Now, the derived subgroup of $F(a, b)$ is a characteristic subgroup and so automorphisms are preserved under the abelianization map $F(a, b)\rightarrow \mathbb{Z}\times\mathbb{Z}$. So there exists a map $\phi: \operatorname{Aut}(F(a, b))\rightarrow\operatorname{Aut}(\mathbb{Z}\times\mathbb{Z})$. Now, suppose $\alpha_1=\alpha_2\pmod{\operatorname{Inn}(F(a, b))}$. Then there exists an inner automorphism $\gamma$ (corresponding to conjugation by some $g\in F(a, b)$) such that $\alpha_1=\alpha_2\gamma$. That is, there exists some $g\in F(a, b)$ such that for all $h\in F(a, b)$ we have that $\alpha_1(h)=g^{-1}\alpha_2(h)g$. Therefore, under the abelinisation map $\alpha_1$ and $\alpha_2$ act identically. Hence, we can factor the above map $\phi$ as: $$\operatorname{Aut}(F(a, b))\rightarrow\operatorname{Out}(F(a, b))\rightarrow\operatorname{Aut}(\mathbb{Z}\times\mathbb{Z}).$$ A similar "factorisation" always holds, no matter the group. However, the free group of rank two is special, as Nielsen in the 1920s proved that the map $\operatorname{Out}(F(a, b))\rightarrow\operatorname{Aut}(\mathbb{Z}\times\mathbb{Z})$ is an isomorphism. Which is really pretty and means that $\operatorname{Out}(F(a, b))\cong\operatorname{GL}_2(\mathbb{Z})$.
Outer automorphism groups are extremely natural groups to study. For example:
[the example stated above.] $\operatorname{Out}(F_2)\cong\operatorname{GL}_2(\mathbb{Z})$, where $F_2$ is the free groups of rank two.
Let $\Sigma_g$ be a closed, orientable surface of genus $g$, and write $\operatorname{MCG}^{\pm}(\Sigma_g)$ for its extended mapping class group (so the quotient group of the space of all homeomorphisms, rather than of just the orientation-preserving ones). Then $\operatorname{Out}(\pi_1(\Sigma_g))\cong\operatorname{MCG}^{\pm}(\Sigma_g)$.
Let $H$ and $K$ be groups and suppose $\alpha_1, \alpha_2\in\operatorname{Aut}(H)$. If ${\alpha_1}={\alpha_2}\pmod{\operatorname{Inn}(G)}$ then $H\rtimes_{\alpha_1}K\cong H\rtimes_{\alpha_2}K$.
There does not exist any group $G$ such that $\operatorname{Aut}(G)\cong\mathbb{Z}$. However, for every group $H$ there exists some group $G$ such that $\operatorname{Out}(G)\cong H$.
My original answer misread the question and so the answer is orthogonal to what you are actually asking. As it had some up-votes, I will keep it deleted.
Your proposed statement is false. Here's a counterexample:
Let $G=\mathbb{Z}$. Then there is no group $A$ such that $\mathrm{Inn}(A)\cong\mathrm{Aut}(G)\cong C_2$. In particular, there can be no group $A'$ satisfying the conditions you give.
That no such $A$ exists follows from the following well-known proposition:
Proposition. Let $G$ a group, and let $N\leq Z(G)$. If $G/N$ is cyclic, then $G$ is abelian.
This has been proven many times in this site.
In particular, $\mathrm{Inn}(A)$ cannot be cyclic and nontrivial, because $\mathrm{Inn}(A)\cong G/Z(G)$; this is the case in the example above, since $\mathrm{Aut}(\mathbb{Z})$ is cyclic of order $2$. Thus, there is no group $A$ such that $\mathrm{Inn}(A)\cong\mathrm{Aut}(\mathbb{Z})$. In particular, there can be no group $A$ that contains a normal copy of $\mathbb{Z}$ and satisfies $\mathrm{Inn}(A)\cong\mathrm{Aut}(\mathbb{Z})$.
Likewise, using primitive roots, we have that $\mathrm{Aut}(\mathbb{Z}_n)$ is cyclic for any $n$ that is an odd prime power, twice an odd prime power, $n=2$, and $n=4$; for all those values of $n$ except for $n=2$, there can be no $A$ with $\mathrm{Inn}(A)\cong \mathrm{Aut}(\mathbb{Z}_n)$. In particular, there is no group $A$ that contains a copy of $\mathbb{Z}_n$ as a normal subgroup and has inner automorphism group equal to the automorphism group of $\mathbb{Z}_n$. So the proposition cannot be rescued even if we restrict to finite groups.
On the other hand, Takao Matsumoto proved that every group is isomorphic to the outer automorphism group of some group (Any group is represented by an outerautomorphism group. Hiroshima Math. J. 19 (1989), no. 1, 209–219, MR 1009671 (90g:20051)), and more recently it was proven that every group is the outer automorphism group of a simple group.
As to your initial paragraph: if $G$ is centerless, then you can certainly take $A=\mathrm{Aut}(G)$; then $G\cong \mathrm{Inn}(G)\triangleleft \mathrm{Aut}(G)$, and the elements not in $G$ act by conjugation on $\mathrm{Inn}(G)$ inducing an automorphism of $G$ that is not inner.
Best Answer
Since you're working on $S_6$ for class, I won't answer that one for you. But I have another easy example of an outer automorphism.
The Quaternion group $Q_8$ can be represented as $\{1, -1, i, -i, j, -j, k, -k\}$, where $ij=k$, $jk=i$, $ki=j$, and $ji=-k$, $kj=-i$, $ik=-j$. The $-1$ element acts pretty obviously on the rest, e.g. $(-1)j=-j$. I think conceptually this is an easy presentation to work with.
So, $Q_8$ has $4$ proper nontrivial subgroups: $Z=\{1,-1\}$ (which is characteristic, and equal to both the center and commutator subgroups), $I=\{1,-1,i,-i\}$, $J=\{1,-1,j,-j\}$, and $K=\{1,-1,k,-k\}$.
All of these subgroups are normal, so there is no element in $x \in Q_8$ for which $I^x=J$, for example. Perhaps an inner automorphism will permute elements nontrivially within those three subgroups, but it won't move the subgroups themselves.
However, it's pretty clear just from looking at $I$ $J$ and $K$ that there's no real difference between these subgroups. If we changed $i$'s name to $j$, $j$'s name to $k$, and $k$'s name to $i$, this wouldn't mess up the group in any way - so, we can expect that a mapping $\sigma:i\mapsto j, j\mapsto k, k\mapsto i$ defines an automorphism of $Q_8$. In other words, this outer automorphism permutes the set of subgroups $\{I,J,K\}$. As a matter of fact, the outer automorphism group of $Q_8$ turns out to be $S_3$, and acts by permuting this set of three subgroups.
EDIT: I wanted to add another thing, a heuristic I use when thinking about automorphisms in general. I find it helpful, for some reason, to think about contructing an isomorphism from $G$ to $G$ (as if $G$ were some different group I was trying to prove isomorphic to $G$). To me this is very intuitive especially when considering outer automorphisms, as inner automorphisms do have that concrete definition using group elements, but outer automorphisms don't. This helped me to better understand what "characteristic" subgroups are - for example, any automorphism (outer or not) of $Q_8$ had better map $-1$ to $-1$, because it's the only element that acts like that. The same holds for the center of any group, the commutator subgroup of any group, normal (and hence unique) Sylow subgroups, any term of the derived, upper central, lower central, fitting, or frattini series, and so on. Anything that is uniquely defined using only properties of the group must be fixed by any automorphism, because if $G$ is isomorphic to $G$, the isomorphism between them must send those subgroups to the same place. Note that, as the comment points out, this heuristic requires some additional thought when the group is not finite.