Let $\phi:G \to G$ be the automorphism. We'll prove $\phi(P)$ is a $p$-Sylow Subgroup of $G$.
$\phi$ takes identity to itself:
For any $e_G \in G$, the identity in G, $\phi(e_G.e_G)=\phi(e_G)\phi(e_G)$
which proves the result.(from cancellation law in a group)
$\phi$ takes inverses to inverses:
Use the fact that $gg^{-1}=e_G$ for any $g \in G$. Do a computation similar to the one above.
$\phi$ takes subgroups to subgroups:
Let $H \leq G$. We intend to prove $\phi(H)$ is a subgroup. Use the 'lemma' we have proved before and verify the subgroup criterion (that $\phi(H)$ is closed under multiplication and inverses. )
Now, by one of my comments above, (in fact by just using the bijectivity of the map $\phi$, and by looking at its restriction to $H$), we'll prove that $|\phi(H)|=|H|$.
Note that the definition for two sets to be of same cardinality is that there exists a bijection between them.
So, You are through.
I think the $S_5$ work is correct (sorry, haven't looked at the $A_5$ work). I would do it a somewhat different way:
Since 5, but not 25, divides 120 (the size of $S_5$), the Sylow-5 subgroups of $S_5$ must be cyclic of order 5. There are 24 5-cycles in $S_5$, 4 of them in each of these subgroups, so, 6 Sylow-5 subgroups.
Similarly, the Sylow-3 subgroups must be cyclic of order 3. There are 20 3-cycles in $S_5$, 2 to a subgroup, so 10 Sylow-3 subgroups.
Since 8, but not 16, divides 120, the Sylow-2 subgroups must have order 8. Now, $S_4$ contains three copies of the dihedral group of order 8, and $S_5$ contains 5 copies of $S_4$, so I get 15 Sylow-2 subgroups.
Something like this ought to work for $A_5$.
EDIT: I think OP wants me to elaborate on the dihedral-group part of the argument.
Take a square, label its vertices, cyclically, with 1, 2, 3, 4. Then the element $(1234)$ of $S_4$ has a natural interpretation as the rotation, one-fourth of the way around, of the square, and the element $(13)$ is the flip in the diagonal through 2 and 4, so these two elements of $S_4$ generate a subgroup isomorphic to the dihedral group of order 8.
The same is true for the elements $(1342)$ and $(14)$, and also for the elements $(1423)$ and $(12)$, and those are the three copies of the dihedral group in $S_4$.
Now if you pick any one of the numbers 1, 2, 3, 4, 5, and consider all the elements of $S_5$ that fix that number, you get a subgroup of $S_5$ isomorphic to $S_4$. Those are your five copies of $S_4$ in $S_5$.
Best Answer
elements of $A_5$ are totally explicit. 5-Sylow are cyclic of order $5$ , generated by a $5$-cycle. So, pick for example $s=(1 \ 2 \ 3 \ 4 \ 5)$ . I am pretty sure that if you pick a random element $t$ of $A_5$, $tst^{-1}$ won't be a power of $s$.
You cannot expect a general reasonable answer( except the trivial one: given a subgroup $H$ of $G$, compute $gHg^{-1}$ ofr all $g\in G$ and see if it is contained in $H$. Of course you can use generators of $H$ and/or $G$ to reduce to a small number of verifications, but still...)
To prove my point: any group $G$ with odd order has a non trivial normal subgroup. I really doubt that if I give you a group $G$ of huge odd order and a subgroup $H$, you will be able to decide if $H$ is normal or not.
Proving that a given group does or does not have a nontrivial normal subgroup is difficult. For example, the classification of finite simple groups took decades of efforts, and involves extremely difficult mathematics.