Question

If p is prime, how many elements of$\left\{0,1,...p^n-1\right\}$ have an inverse modulo${\mathbf{p}}^{\mathbf{n}}$ ?

Short answer

The total number of inverses is${\mathrm{P}}^{\mathrm{n}}–1(\mathrm{P}-1).$ .

Step-by-step solution

Introduction

The modular inverse of $\mathrm{A}\mathrm{mod}\mathrm{C}$is the B value that makes$\mathrm{A}*\mathrm{B}\mathrm{mod}\mathrm{C}=1$ . The modular multiplicative inverse can be defined as the$\mathrm{GCD}(\mathrm{a},\mathrm{b})$ must be equal to 1 and$‘\mathrm{a}’\mathrm{and}‘\mathrm{b}’$ are relatively prime.

Inverse modulo of pn

Given elements are, $\left\{0,1,...{\mathrm{p}}^{\mathrm{n}}-1\right\}$.

If is a prime, then for all given elements i.e. $\left\{0,1,...{\mathrm{p}}^{\mathrm{n}}-1\right\}$, it is not the multiple of p and it contains the inverse of $p^n$.

We have given that the range of elements is$\left\{0,1,...{\mathrm{p}}^{\mathrm{n}}-1\right\}$

Now,${\mathrm{p}}^{\mathrm{n}}-1$ is the only element that get divisible by$p^n$ .

So, total number of inverses are,

${\mathrm{P}}^{\mathrm{n}}–{\mathrm{P}}^{\mathrm{n}}–1={\mathrm{P}}^{\mathrm{n}}–1(\mathrm{P}-1)$

Therefore, total number of inverse is${\mathrm{P}}^{\mathrm{n}}–1(\mathrm{P}-1)$ .