3
$\begingroup$

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.

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

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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