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}$?
 A: 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$.
A: 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.)
A: 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?  
A: 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.
A: 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*}
A: 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.
A: 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.$
A: 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
$$
