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$
  • 1
    $\begingroup$ If $gcd(n,p^k) > 1$ then $gcd(n,p) > 1$ so that $n = mp$ for some $m$ $\endgroup$ – reuns Feb 14 '17 at 17:40
  • $\begingroup$ There is a nice proof involving the Moebius function, but I guess it's too advanced. $\endgroup$ – Batominovski Feb 14 '17 at 17:41
  • $\begingroup$ @user1952009 And ... ? $\endgroup$ – temo Feb 14 '17 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 '17 at 17:43
  • 1
    $\begingroup$ @temo The Pythagorean theorem isn't trivial at all in Euclidean geometry. $\endgroup$ – reuns Feb 14 '17 at 17:47
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$
  • $\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 '17 at 20:49
5
$\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$
  • $\begingroup$ $\simeq$ as what ? $\endgroup$ – reuns Feb 14 '17 at 17:45
  • $\begingroup$ @user1952009: What do you mean: some details on the isomorphism? $\endgroup$ – Bernard Feb 14 '17 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 '17 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$ – Alex Mathers Feb 14 '17 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 '17 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$
  • $\begingroup$ Same as the proof in my answer. $\endgroup$ – Bill Dubuque Feb 16 '17 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 '17 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
$\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$
  • $\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 '17 at 14:24
  • $\begingroup$ $\phi(p^k)$ counts integers coprime to $p^k$, so $p^k$ itself doesn't count. $\endgroup$ – JonMark Perry Feb 22 '17 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 '17 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.