Show that $\phi(p^e)=p^e-p^{e-1}$
The supplementary question has nothing to do with the abstract Chinese remainder theorem. It doesn't require induction either.
$\varphi(p^{e})$ is the number of classes of integers which are units modulo $p^e$. Each such class of congruence has a unique representative in the form $\;a_0+a_1 p+\dots a_{e-1} p^{e-1},\quad 0\le a_0,a_0,\dots a_{e-1}\le p-1 $ (to see this, write any integer in base $p$).
Now any $n=a_0+a_1 p+\dots a_{e-1} p^{e-1}$ is a unit mod. $p^e$ if and only if $a_0\ne 0$, while the $a_i$s, for $i\ge 0$ can have any value. Thus the distinct representatives for units mod. $p^e$ are $$(p-1)p^{e-1}=p^e-p^{e-1}\quad\text{in number}.$$
Related videos on Youtube
samantha
Updated on February 10, 2020Comments
-
samantha over 3 years
In an exercise I was asked to show that if $R$ is a ring with relatively prime ideals $I_1,I_2$ then $R/I \cong R/I_1 \oplus R/I_2$ where $I=I_1 \cap I_2$ and $\oplus$ is the direct sum. A follow on exercise asks to show, using the above result, that $\varphi(mn)=\varphi(m) \varphi(n)$ provided that gcd($m,n)=1$ and $\varphi$ is the Euler-Phi function. It then asks to show also that $\varphi(p^e)=p^e-p^{e-1}$ if $p$ is prime. How am I supposed to show that $\varphi(p^e)=p^e-p^{e-1}$ using the above result? Or is it unrelated?
-
DonAntonio over 7 yearsI think it is unrelated, and a simple counting (perhaps with induction) gives the equality.
-
Dietrich Burde over 7 yearsFor a simple proof see here. Then we can write $n=p_1^{e_1}\cdots p_r^{e_r}$ and use that $\phi$ is multiplicative to compute $\phi(n)$.
-
Viktor Vaughn over 7 yearsThere are several proofs here. As Dietrich says, knowing that $\phi$ is (number-theoretically) multiplicative means that its action on prime powers determines it completely.
-