I want to understand how to count power residue modulo a fixed integer. More precisely I would like to count the residues of the form $x^k$ in the group of units of $Z/p^a Z$. I am told that it is $$\phi(p^a) /(k, \phi(p^a))$$
for most of the cases of a and p, but I do not understand how it is so. Has the Chinese remainder theorem have something to do rewriring this questions in a more handball way?
Hint 1: Use the fact that if $p$ is odd then $(\Bbb{Z}/p^a\Bbb{Z})^{\times}$ is cyclic of order $\phi(p^a)$, and if $p=2$ is even and $a>1$ then $$(\Bbb{Z}/p^a\Bbb{Z})^{\times}\cong(\Bbb{Z}/2\Bbb{Z})\times(\Bbb{Z}/2^{a-1}\Bbb{Z}).$$
Hint 2: In a cyclic group of order $n$, every element is a $k$-th power if $\gcd(k,n)=1$. If $k\mid n$ then the $k$-th powers are precisely the elements of orderd dividing $\tfrac{k}{n}$.