2
$\begingroup$

Are there any short, elegant proofs known for the identity $\varphi(p^{k})=p^{k}-p^{k-1}$ ? (Here $\varphi$ is Euler's totient function and $p$ is a prime.)

The standard combinatorial proof goes like this:

In the set $\left\{ 1,2\ldots,p^{k}\right\} $ there in total $p^{k}$ number. Split this set into $p$ subsets $\left\{ 1,\ldots,p\right\} $, $\left\{ p+1,\ldots,2p\right\} \ldots$ Then in each of these sets there is only one number -- namely the one of the form $m\cdot p$ for some suitable $m$, that divides $p^{k}$. There are in total $\frac{p^{k}}{p}=p^{k-1}$ such sets, so in total $p^{k-1}$-many number from $\left\{ 1,2\ldots,p^{k}\right\} $ divide $p^{k}$. Thus $(p^{k}-p^{k-1})$-many numbers are coprime to $p^k$, which proves the identity. $\square$

(A different proof that is often encountered assumes that we know that $\varphi(n)=n\prod_{p\mid n}(1-\frac{1}{p})$, from which our identity follows immediately. But this is actually a longer proof, since proving the auxiliary identity is longer.)

Surprisingly, I would have imagined that there are tons of wildly different proofs of such a basic fact out there, but a preliminary internet seach as well as book skimming returned only (minor variations of) these two proofs.

EDIT The present proofs are more or less reformulations (very polished with details hidden as good as possible - but still reformulations) of my first proofs. What I'm looking for are more radically different approaches (if these exist).

$\endgroup$
13
  • 1
    $\begingroup$ If $gcd(n,p^k) > 1$ then $gcd(n,p) > 1$ so that $n = mp$ for some $m$ $\endgroup$
    – reuns
    Feb 14, 2017 at 17:40
  • $\begingroup$ There is a nice proof involving the Moebius function, but I guess it's too advanced. $\endgroup$ Feb 14, 2017 at 17:41
  • $\begingroup$ @user1952009 And ... ? $\endgroup$
    – temo
    Feb 14, 2017 at 17:41
  • 1
    $\begingroup$ @temo There are $p^{k-1}$ possible values for $m$... This is trivial, elegant-proofs are for non-trivial things. $\endgroup$
    – reuns
    Feb 14, 2017 at 17:43
  • 1
    $\begingroup$ @temo The Pythagorean theorem isn't trivial at all in Euclidean geometry. $\endgroup$
    – reuns
    Feb 14, 2017 at 17:47

8 Answers 8

6
$\begingroup$

A beautiful proof for the second identity you mention is probabilistic :

Take the set $\{1,...,n\}$ with the uniform probability measure (i.e. $P(\{i\}) = 1/n$ for any $i\in \{1,...,n\}$).

Then $\phi(n)/n = P(\{k, gcd(n,k) = 1\}) = P(\{k, \forall p$, prime, $(p$ divides $n) \implies (p$ doesn't divide $k)\} = P(\displaystyle\bigcap_{p\mid n} \{k, p$ doesn't divide $k\})$. Now it is easily proved that the events $(\{k, p$ divides $k\})_{p\mid n}$ are independent (just compute it) and so their complements are as well, which shows that

$\phi(n)/n = \prod_{p\mid n}(1- 1/p)$

That lets you conclude

$\endgroup$
5
$\begingroup$

Hint $\,\ \gcd(a,p^k)>1 \iff p\mid a \iff a\, \equiv\,\overbrace{ 1p,\,2p,3p,\ldots,\color{#c00}{p^{k-1}}p}^{\large\quad\color{#c00}{p^{\Large k-1}}\ \rm elements}\,\pmod{\!p^k}$

Thus there are $\,\color{#c00}{p^{k-1}}$ non-coprime residues, so $\,p^k - \color{#c00}{p^{k-1}}$ coprime residues mod $p^k$.

$\endgroup$
4
$\begingroup$

Yes, a one-line proof: $$(\mathbf Z/p^k\mathbf Z)^\times= \mathbf Z/p^k\mathbf Z\smallsetminus (p\mathbf Z/p^k\mathbf Z),\enspace\text{and}\quad p\mathbf Z/p^k\mathbf Z\simeq\mathbf Z/p^{k-1}\mathbf Z. $$ And a detail on a second line (well, a sesquiline…) for the isomorphism: \begin{align}p\mathbf Z/p^k\mathbf Z&\longrightarrow\mathbf Z/p^{k-1}\mathbf ,\\ px+p^k\mathbf Z&\longmapsto x+p^{k-1}\mathbf Z. \end{align}

$\endgroup$
8
  • $\begingroup$ $\simeq$ as what ? $\endgroup$
    – reuns
    Feb 14, 2017 at 17:45
  • $\begingroup$ @user1952009: What do you mean: some details on the isomorphism? $\endgroup$
    – Bernard
    Feb 14, 2017 at 17:47
  • $\begingroup$ Hm...I'll have to think a bit about this, if this does not make too much use of "advanced machinery". In any case, could you please elaborate (another one-liner would be enough) how to establish the isomorphism ? $\endgroup$
    – temo
    Feb 14, 2017 at 17:48
  • $\begingroup$ @temo it's simple; there is a natural map $\Bbb Z\to p\Bbb Z$ and a natural map $p\Bbb Z\to p\Bbb Z/p^k\Bbb Z$. Compose the two and check that the kernel is $p^{k-1}\Bbb Z$. $\endgroup$ Feb 14, 2017 at 17:51
  • $\begingroup$ Ah thanks. Number theory is sooo far away from me now, that I got a bit rusty. $\endgroup$
    – temo
    Feb 14, 2017 at 17:54
3
$\begingroup$

Among the numbers in $\{1,2,\ldots,p^k\}$ exactly $p^{k-1}$ have at least one factor $p$. Since $p^k$ has no prime factors other than $p$ it follows that $\phi(p^k)=p^k-p^{k-1}$.

$\endgroup$
2
  • $\begingroup$ Same as the proof in my answer. $\endgroup$ Feb 16, 2017 at 19:41
  • 1
    $\begingroup$ Which in turn is, at the core, the same as the proof in my question (though in a slicker dress)... $\endgroup$
    – temo
    Feb 17, 2017 at 19:25
2
$\begingroup$

Denote by $C_r$ the cyclic group of order $r$ and by $g_r$ the number of generators of $C_r$. Then for a prime $p$ the homomorphism $C_{p^k} \rightarrow C_{p^{k-1}}: g \mapsto g^p$, for $k>1$, maps generators onto generators and the size of a preimage of an element by the homomorphism is $p$ so $g_{p^k} = pg_{p^{k-1}}$. for the case $k = 1$ obviously $g_p = p-1$, so by induction we have $g_{p^k} =p^{k-1}(p-1)$.

$\endgroup$
1
+150
$\begingroup$

$\mathbf Z/n\mathbf Z$ is an additive group with $n$ elements and has $\varphi(d)$ elements of order $d$ for each divisor $d$ of n. This is a well known fact that leads to Gauss 'formula: $$\sum_{d|n} \varphi(d) = n$$ So $$p^{k+1} = \sum_{d|p^{k+1}} \varphi(d) = \varphi(p^{k+1}) + \sum_{d|p^k} \varphi(d) = \varphi(p^{k+1}) + p^k$$ and $$\varphi(p^{k+1}) = p^{k+1} - p^k = p^k (p-1)$$ QED

$\endgroup$
1
  • $\begingroup$ I gave you the bounty, as I felt that this proof was conceptually the most beautiful one, as a lot of not-so-beautiful technical details (even though they're the same as in the other proofs) are completely hidden away in this formulation. $\endgroup$
    – temo
    Feb 21, 2017 at 20:49
1
$\begingroup$

As the only prime that divides $p^k$ is $p$, we only need to look at integers in $\{1,\dots,p^k-1\}$ that have $p$ as a factor.

There are precisely $p^{k-1}-1$ of these.

So $\phi(p^k)=(p^k-1)-(p^{k-1}-1)=p^k-p^{k-1}$.

$\endgroup$
3
  • $\begingroup$ Why not simply look at integers in $\{1,\ldots,p^k\}$ instead? Then you save having to add "$-1$" four times. $\endgroup$
    – Erick Wong
    Feb 22, 2017 at 14:24
  • $\begingroup$ $\phi(p^k)$ counts integers coprime to $p^k$, so $p^k$ itself doesn't count. $\endgroup$
    – JMP
    Feb 22, 2017 at 15:46
  • $\begingroup$ Of course, what I'm saying is that if you include this in your counting then you immediately get $p^k - p^{k-1}$ instead of having to cancel out the $-1$s. Not excluding $p^k$ a priori is less cumbersome and adheres closer to the general definition of $\phi$. $\endgroup$
    – Erick Wong
    Feb 22, 2017 at 18:17
0
$\begingroup$

Curiously nobody has used the product form of the Euler totient's function. If you are still interested, here is a proof more on the analytical side of the theory.

Since

$$ \varphi(n) = n \prod_{p|n} \left( 1-\frac{1}{p} \right), $$

replace $n=p^\alpha$ and you are done. The proof of the formula you can find it here.

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