Is there a direct, elementary proof of $n = \sum_{k|n} \phi(k)$?

If $k$ is a positive natural number then $\phi(k)$ denotes the number of natural numbers less than $k$ which are prime to $k$. I have seen proofs that $n = \sum_{k|n} \phi(k)$ which basically partitions $\mathbb{Z}/n\mathbb{Z}$ into subsets of elements of order $k$ (of which there are $\phi(k)$-many) as $k$ ranges over divisors of $n$.

But everything we know about $\mathbb{Z}/n\mathbb{Z}$ comes from elementary number theory (division with remainder, bezout relations, divisibility), so the above relation should be provable without invoking the structure of the group $\mathbb{Z}/n\mathbb{Z}$. Does anyone have a nice, clear, proof which avoids $\mathbb{Z}/n\mathbb{Z}$?

• Commented Mar 22, 2014 at 5:34

Write the fractions $1/n,2/n,3/n \dots ,n/n$ in the simplest form and you can observe that each fraction is of the form $s/t$ where $t$ divides $n$ and $(s,t)=1$. So the number of the fractions is the same as $\sum_{k|n}{\phi(k)}$ which is equal to $n$.

• It might be worth noting that reducing to lowest common terms does not "equalize" any of the $n$ fractions (they remain unequal as before). Commented Sep 12, 2012 at 14:43
• @hardmath: Actually, that's not even required. Anyone who feels like $\frac24\ne\frac12$ still keeps $n$ objects with all divisors $d$ occuring as denominator etc. Commented Sep 12, 2012 at 14:52
• This is perhaps my favorite proof of this result. I believe I first encountered it in Hardy and Wright's book on number theory, but I could be wrong. Commented Sep 12, 2012 at 15:07
• @ChrisLeary, it's my favorite proof too. And you're right, it's in Hardy and Wright, §16.2, at least in my 5th ed.
– lhf
Commented Sep 13, 2012 at 0:09

Clearly $n$ counts the number of elements in the set $\{1,\ldots,n\}$. This suggests that to get a combinatorial proof we should count the number of elements in this set in a different way and get $\sum_{k \mid n} \varphi(k)$.

For $k \mid n$, let $S(k)$ be the set of $m \in \{1,\ldots,n\}$ such that $\gcd(m,n) = k$. Since for all $m \in \{1,\ldots,n\}$, $\gcd(m,n)$ is a divisor of $n$, we have $\sum_{k \mid n} \# S(k) = n$.

Now I claim that for all $k \mid n$, $\# S(k) = \varphi(\frac{n}{k})$. This implies the result because as $k$ runs through all positive divisors of $n$ so does $\frac{n}{k}$. Can you see how to establish this equality?

• Yes I can see how to establish that equality. Very nice! Commented Sep 12, 2012 at 14:56
• @JessicaB But this is basically the same proof as the one you mentioned in your original question, just phrased slightly differently. To say that $\gcd(m,n)=k$ is the same as saying that $m$ has order $n/k$ in the group $\mathbb{Z}/n\mathbb{Z}$.
– Ted
Commented Sep 12, 2012 at 16:01
• @Ted I think my question was phrased sufficiently clearly to convey that I was expecting an elementary number theory re-phrasing of "the same proof." That said, I disagree with the spirit of your assertion, for the following reason: in order to "see it from the group structure of $\mathbb{Z}/n\mathbb{Z}$," one is actually required to write a lot more. Can we really say that two proofs are 'basically the same' if they use the same ingredients, but one is much longer and introduces needless language? (order, generator, etc). Commented Sep 12, 2012 at 17:46
• So the people reading this answer years later who do not see "how to establish the equality" are just screwed? Commented Aug 25, 2019 at 1:58
• I would like to think that we induce a partition on the set $\{1,2,\ldots, n\}$ using an equivalence relation $\sim$. Define $a\sim b$ iff $\text{gcd}(a,n)=\text{gcd}(b,n)$. This is an equivalence relation! Commented Oct 30, 2023 at 3:36

Consider all proper fractions of the form $$a/n$$. There are $$n$$ of those. When you consider their reduced forms you get fractions of the form $$b/d$$ with $$d|n$$ and $$\gcd(b,d)=1$$. There are $$\phi(d)$$ of those. The result follows.

Here is a proof using induction on $n$. The case $n=1$ is clear as $\phi(1)=1$.

Let $n>1$ and assume the result for positive integers less than $n$. Choose a prime divisor $p$ of $n$ and write $n=mp^k$ for $m$ and $p$ coprime. The divisors of $n$ are precisely the $dp^i$ for $d|m$ and $0\leq i\leq k$, so we obtain

\begin{align*} \sum_{d|n}\phi(d)&=\sum_{i=0}^{k}\sum_{d|m}\phi(dp^i)=\sum_{i=0}^{k}\phi(p^i)\sum_{d|m}\phi(d)=m\sum_{i=0}^{k}\phi(p^i)\\ &=m\left(1+\sum_{i=1}^{k}(p^i-p^{i-1})\right)=mp^k=n. \end{align*}

This proof uses Möbius inversion, and is pretty quick! Recall the function $$\mu(n) = \begin{cases} (-1)^{\nu(n)} \qquad \text{if n is square free} \\ 0 \,\,\qquad\qquad\text{otherwise}, \end{cases}$$ where $\nu(n)$ is the number of distinct prime divisors of $n$. The Möbius inversion formula says that $$f(n)=\sum_{d\mid n} g(d)$$ if and only if $$g(n)=\sum_{d\mid n}\mu(d)f(n/d).$$ Putting $f(n)=n$ and $g(n)=\varphi(n)$, by Möbius it suffices to show $$\varphi(n)=\sum_{d\mid n}\mu(d)\frac{n}{d},$$ and this is true since \begin{align*} \varphi(n)&=n \prod_{p\mid n}\bigg(1-\frac{1}{p}\bigg)\\ &=n \sum_{d\mid n}\frac{\mu(d)}{d}\\ &=\sum_{d\mid n}\mu(d)\frac{n}{d}. \end{align*}

(Note that $\prod_{p\mid n}\big(1-\frac{1}{p}\big)=\sum_{d\mid n}\frac{\mu(d)}{d}$ since terms in the sum are zero except at divisors of $d$ that consist of distinct primes, and multiplying out the product on the right gives precisely this sum.)

For a prime $$p$$ and $$k\ge1$$, $$\phi\!\left(p^k\right)=(p-1)p^{k-1}\tag1$$ Furthermore, the result is true for powers of a prime: \begin{align} \sum_{d|p^m}\phi(d) &=\phi(1)+\sum_{k=1}^m\phi\!\left(p^k\right)\tag{2a}\\ &=1+(p-1)\sum_{k=1}^mp^{k-1}\tag{2b}\\ &=1+(p-1)\frac{p^m-1}{p-1}\tag{2c}\\[9pt] &=p^m\tag{2d} \end{align} Given $$(m_1,m_2)=1$$, for every $$d$$ so that $$d|m_1m_2$$, that there are unique $$d_1$$ and $$d_2$$ so that $$d=d_1d_2$$ and $$d_1|m_1$$ and $$d_2|m_2$$. Thus, $$\sum_{d_1|m_1}\phi(d_1)\sum_{d_2|m_2}\phi(d_2)=\sum_{d|m_1m_2}\phi(d)\tag3$$ Therefore, since $$\phi$$ is multiplicative, $$m\mapsto\sum\limits_{d|m}\phi(d)$$ is multiplicative.

$$(2)$$ and $$(3)$$ show that $$\sum_{d|n}\phi(d)=n\tag4$$

I have a pretty cool inductive proof.

The Base Case is trivial.

Now, assume that for some positive integer $m$ we had

$\sum_{m|n} \phi(m) = n$

Now, I will show that for any prime power $p^d$, we must have $\sum_{m|p^dn} \phi(m) = p^dn$

For the sake of convenience, we may assume that $\gcd(p,n) = 1$. If this was not the case, just repeat the proof but instead of using $n$ use $\frac{n}{\text{ord}_p(n)}$ instead.

Now,

\begin{align} \sum_{m|p^dn} \phi(m) &= \sum_{m|n} \phi(m) + \sum_{p|m|pn} \phi(m) + ... + \sum_{p^d|m|p^dn} \phi(m) \\ &= n+\sum_{k|n} \phi(p)\phi(k) + \sum_{k|n} \phi(p^2)\phi(k) + ... + \sum_{k|n} \phi(p^d)\phi(k) \\ &= n+\phi(p)*n+\phi(p^2)*n+...+\phi(p^d)*n \\ &= n(1+(p-1)+p(p-1)+p^2(p-1)+...+p^{d-1}(p-1)) \\ &= n(1+(p-1)\frac{p^d-1}{p-1}) \\ &= n*p^d \end{align}

thus proving the inductive step thus completing the proof.

• The base case consists of showing the equality holds for all primes $n$ (I guess that's what you called trivial?) but you also need to prove that the inductive step does not just work for prime powers, but for any composite $n = p \cdot q$.
– TMM
Commented Oct 1, 2016 at 21:41

Claim:Number of positive integers pair $(a, b)$ satisfying : $n=a+b$ (for given $n$) $\gcd(a, b) =d$ and $d|n$ is $\phi(n/d)$.

Proof: Let $a=xd$ and $b=yd$ We want number of solution for $x+y=\frac{n}{d}$ such that $\gcd(x, y) =1$.

$\gcd(x,y)=\gcd(x,x+y)=\gcd(x,n/d)=1$

Solution for $x+y=n/d$, $\gcd(x,y)=1$ is $\phi(n/d)$. ________________________

Number of positive integers pair $(a, b)$ satisfying $a+b=n$ is $n$.

But this can counted in different way: If $(a, b)$ is solution then $\gcd(a, b) =d$ for some divisor $d$ of $n$.

So we can use our claim to write $\sum_{d|n} \phi(n/d) =\sum_{d|n}\phi(d)=$ Number of solution $=n.$