# Proof of the following property about prime numbers [closed]

Is there a proper proof of the following property:

Let $p$ be a prime number. The number of invertible elements in $\mathbb{Z}/p^n\mathbb{Z}$ is $(p-1)p^{n-1}$.

## closed as off-topic by user26857, Davide Giraudo, C. Falcon, user228113, ThomasJul 11 '16 at 23:15

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – user26857, Davide Giraudo, Thomas
If this question can be reworded to fit the rules in the help center, please edit the question.

• What makes a proof proper? – vadim123 May 17 '16 at 15:36
• Yes, there is.${}$ – user228113 Jul 11 '16 at 21:49

## 2 Answers

An element $\overline{a}$ (where $0\leq a \leq n-1)$ of the ring $\mathbb{Z}/n$ is invertible precisely when $a$ is coprime to $n$ by a standard result of elementary number theory. The number of positive integers less than or equal to $n$ which are coprime to $n$ is given by the euler-phi function.

Hence it suffices to compute $\varphi(p^n)$. You can show that $\varphi(p^n)=(p-1)p^{n-1}$ by noting that the only postive integers less than or equal to $p^n$ which are not coprime to it are the multiples of $p$ namely $kp$ for $k=1,\dotsc, p^{n-1}$. Hence $$\varphi(p^n)=p^n-p^{n-1}=(p-1)p^{n-1}.$$

Let $G=\mathbb{Z}/p^{n}\mathbb{Z}$.

Lemma. For $a,n\in\mathbb{N}$, $ax\pmod{m}=1$ has a solution if and only if $\gcd(a,m)=1$.

Proof. $ab\pmod{m}=1\iff m\mid ab-1\iff\exists k\in\mathbb{N}$ such that $mk=ab-1\iff1=a(b)+m(-k)\iff\gcd(a,m)=1$.//

Now, by our lemma we know that the invertible elements in $G$ are precisely those that are relatively prime to $p^{n}$. If you are familiar with the Euler-totient function, then you know that the number of such elements is $\varphi(p^{n})=p^{n}-p^{n-1}=(p-1)p^{n-1}$.