If $p$ is a prime, how many elements of $\{1, \ldots,( p^n) − 1\}$ have an inverse modulo $p^n$? Question:
If $p$ is a prime, how many elements of $\{1, \ldots , (p^n) − 1\}$ have an inverse modulo $p^n$?
I've been mulling this problem over for days, and I still have absolutely no idea what it is asking or how to even approach it. Any help would be greatly appreciated.
 A: Everybody except the people divisible by $p$. These are $p$, $2p$, and so on up to $(p^{n-1}-1)p$. How many of them are there?
It is somewhat smoother to consider the numbers $1$ to $p^n$, and remove those that are divisible by $p$.  
A: Hint: By the Bezout identity for the gcd, the invertible elements mod $p^n$ are precisely those elements coprime to $p^n$, i.e. coprime to $p$. But a natural $< p^n$ is not coprime to $p$ iff it has form $m p$ for $\:0 \le m < p^{n-1}$. Removing these $p^{n-1}$ non-coprime elements leaves $\ldots$ elements coprime to $p$.
A: More generally one can ask how many elements of $\{1,\ldots,m-1\}$ have an inverse modulo $m$.  The answer is that all of them that have no common divisor with $m$ except $1$.  Thus if the fraction $k/m$ is in lowest terms then $k$ has an inverse modulo $m$ and otherwise it does not.  If $m=p^n$ then $k/m$ is in lowest terms if and only if $k$ is not divisible by $p$.
The number of such numbers is $\varphi(m)$, i.e. Euler's totient function evalutated at $m$.
A: All the elements in the list except the ones that are multiples of $p$. This is because all the numbers in the list are relatively prime to $p$, except the ones that are divisible by $p$.  
