Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

4 Answers 4

up vote 3 down vote accepted

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.