1. The problem statement, all variables and given/known data
This is question 30, section 2.5 from "Abstract Algebra 3rd edition" by Herstein.

2. Relevant information
A subgroup H of group G is called characteristic if for all automorphisms phi of G, phi(H) is a subset of H.

(I paraphrased this from question 29. I don't know why he says "phi(H) is a subset of H" but not "phi(H) and H are the same set". After all, phi is bijective?)

3. The attempt at a solution
Here is what I did: H is a subgroup of order prime, so it is cyclic, generated by any non-identity element in H. Call H<a>.

Let phi be an arbitrary automorphism on G, then phi must map <a> to yet another cyclic subgroup of order p in G, call this <phi(a)>. Since both <a> and <phi(a)> are cyclic, they're either the same subgroup, or only share the identity element.

Let K of be the smallest subgroup generated by every possible products of <a> and <phi(a)>. If <a> and <phi(a)> are different, then the order of K is p^{2}. So p^{2} has to divide pm, which contradicts the fact that p does not divide m. So <a> and <phi(a)> have to be the same subgroup in G.

Hence any automorphism phi on G will also be an automorphism on <a>, which implies that <a>, aka H, is characteristic.

My problem: I never used the fact that H is a normal subgroup. I'm being quite confused. Where was I wrong? Many thanks for the help.

Why must the order of [itex]K[/itex] be [itex]p^2[/itex]? You haven't proved that. All that can be concluded based on what you have written so far is that if [itex]a[/itex] and [itex]\phi(a)[/itex] generate two different subgroups, then any subgroup containing them must have at least [itex]2p - 1[/itex] elements and its order must be divisible by [itex]p[/itex].

jbunniii found your flaw. Now try to fix it. Try to show H is the ONLY normal subgroup of order p. Suppose there are two. Use that the product of normal subgroups is a group.

I made my mistakes when concluding |K| = p^{2} too early. Here was how I came to it:
Suppose a^{i} phi(a)^{j} = a^{k} phi(a)^{l} (where i, j, k, l are integers in range [0, p - 1])
That implies a^{i-k} phi(a)^{j-l} = e
Because we assumed <a> and <phi(a)> were different subgroups, each cannot contain the inverse of another, unless it is the identity element. This implies i = k and j = l.
So a pair of (i, j) uniquely defines an element in <a>*<phi(a)>. There are p^{2} possible combinations.

My mistake is I assumed <a>*<phi(a)> was already a group. It turned out I needed to use the fact that both <a> and <phi(a)> were normal subgroups to come to that conclusion. Thanks Dick for pointing that out.

If my proof still contains any flaw, I'd appreciate any help. Thanks again :)

Your proof is assuming that a and phi(a) commute when you rearranged the powers. That's not necessarily so. You should be able to show the product of two normal subgroups H and H' of order p has order p^2 without assuming that their generators commute.

In post 4 phucnguyen assumes all elements of the group generated by the product can be written as a^i*phi(a)^j moving all of the factors of a to the left and all the factors of phi(a) to the right. That's assuming a and phi(a) commute.

But HK isn't generally a group if neither H nor K is normal. And if HK is not a group, why does its order necessarily have to divide that of G (to obtain the contradiction)?

No. It's just pre-multiplying both sides by a^{-k} and post-multiplying both sides by phi(a)^{-l}. This finds the number of elements in the set (a)(phi(a)) which as you pointed out is also a group because (a) and (phi(a)) are normal subgroups.

That is, in post 4 phucnguyen appears to no longer start by considering the group generated by the product, but only the product itself as a set. Here the elements are defined with powers of a on the left and powers of phi(a) on the right.