Show that $\phi(p^e)=p^e-p^{e-1}$

1,063

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

Share:
1,063

Related videos on Youtube

samantha
Author by

samantha

Updated on February 10, 2020

Comments

  • samantha
    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
      DonAntonio over 7 years
      I think it is unrelated, and a simple counting (perhaps with induction) gives the equality.
    • Dietrich Burde
      Dietrich Burde over 7 years
      For 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
      Viktor Vaughn over 7 years
      There are several proofs here. As Dietrich says, knowing that $\phi$ is (number-theoretically) multiplicative means that its action on prime powers determines it completely.