Number of solutions to $x^k \equiv h \pmod {q^n}$ Could someone please give me a hint/solution to
the question, say $q$ is a prime and $(q,h)=1$, then
$$
x^k \equiv h \pmod {q^n}
$$
has at most $k$ solutions $1 \leq x < q^n$?
Thanks!
 A: This is false as stated. Let $q=2$, $h=1$, $k=2$, $n=3$. Then
$$x^2\equiv 1\bmod 2^3$$
has four solutions $1\leq x<2^3$, namely $x=1,3,5,7$.
A: Let $p$ be an odd prime. Then any positive power $q$ of $p$ has a primitive root. That is, there is a $g$ such that as $i$ travels from $1$ to $\varphi(q)$  the powers $g^i$ travel through the $\varphi(q)$ reduced residue classes modulo $q$. In group-theoretic terms, $g$ generates the group of multiplicative units modulo $q$. Here as usual $\varphi$ is the Euler $\varphi$-function. 
Suppose that $h$ and $q$ are relatively prime, where $q$ is a power of an odd prime.  We will show that the congruence $x^k \equiv h\pmod{q}$, if it has a solution, has precisely $\gcd(k,\varphi(q))$ solutions modulo $q$. As a consequence, the congruence has at most $k$ solutions modulo $q$. 
Suppose that $x^k\equiv h\pmod{q}$. Any such $x$ is congruent to $g^i$ for a suitable $i$, where $1\le i\le \varphi(q)$. Let $h\equiv g^j\pmod{q}$. Then $x^k\equiv h\pmod{q}$ if and only if 
$$g^{ik}\equiv g^j\pmod{q}.$$
The above congruence holds if and only if 
$$ik\equiv j\pmod{\varphi(q)}.$$
But the linear congruence $yk\equiv j\pmod{\varphi(q)}$ has a solution if and only if $\gcd(k,\varphi(q))$ divides $j$. and if it has a solution, it has precisely $\gcd(k,\varphi(q))$ solutions.   
Remark: As pointed out by Zev Chonoles, the result does not hold for powers of $2$ greater than or equal to $2^3$. These numbers do not have a primitive root. The result does hold for $q$ of the form $2p^n$, for $p$ and odd prime, since these $q$ do have a primitive root.   
