# 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.

• So what was the answer? I think I have it but have no way to verify. – Fuerii Sep 30 '16 at 21:09

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$.
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$.
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$.
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$.