Easiest proof for $\sum_{d|n}\phi(d)=n$ To prove $\sum_{d|n}\phi(d)=n$. What is the easiest proof for this to tell my first year undergraduate junior. I do not want any Mobius inversion etc only elementry proof. Tthanks!
 A: Not sure why this is not mentioned: a function $f(n)$ from the positive integers to, for example, the positive integers, is called "multiplicative" in the number theory sense if
$$ \gcd(a,b) = 1 \Longrightarrow f(ab) = f(a) f(b). $$ This definition also works if the values of $f$ are allowed to be fractions, real numbers, complex numbers, whatever. 
Proposition: if $f(n)$ is multiplicative, then 
$$ g(n) = \sum_{d|n} f(d)     $$
is also multiplicative
Proposition: a multiplicative function is determined completely by its values on primes and prime powers
Corollary: two multiplicative functions that agree at primes and prime powers agree for all numbers. 
Proposition: Euler's totient function $\phi(n)$ is multiplicative. 
A: I think the easiest proof is to consider all fractions $\frac k n$ with $1\le k\le n$. 
On the one hand, there are $n$ of those.
On the other hand, after reducing each fraction to lowest terms, you get $\phi(d)$ fractions having denominator $d$. The possible denominators are exactly the divisors of $n$.
A: Write $n = \prod p^{a_p}$
The divisors of $p$ are
$$
\prod p^{b_p}, b_p \le a_p
$$
so the sum on the left hand side is
$$
\sum_{b_2=0}^{a_2}\dots \sum_{b_P=0}^{a_P} 
      \phi(\prod_{p \text{ prime}, p|n, =2}^P p^{b_p})
= \sum_{b_2=0}^{a_2}\dots \sum_{b_P=0}^{a_P} 
\prod_{p \text{ prime}, p|n, b_p>0} \left(1-\frac 1p\right) p^{b_p}
\\  = \prod_{p \text{ prime}, p|n, =2}^P \left[1 + 
\sum_{b_p = 1}^{a_p} \left(1-\frac 1p\right) p^{b_p}
\right] = \prod_{p \text{ prime}, p|n, =2}^P p^{a_p} = n
$$
A: $d\mid n \land S_d=\{m:\gcd(m,n)=d\} \implies \left\lvert S_d \right\rvert=\phi\left(\dfrac{n}{d}\right)$


*

*$S_{d_i}\cap S_{d_j}=\emptyset\ \forall i\neq j$

*$\displaystyle\bigcup_{d \mid n}S_d=\{1,2,\ldots,n\}$ 
$\therefore \left\lvert\displaystyle\bigcup_{d \mid n}S_d\right\rvert=\displaystyle\sum_{d\mid n}\left\lvert S_d\right\rvert\implies n=\displaystyle\sum_{d\mid n}\phi\left(\dfrac{n}{d}\right)=\displaystyle\sum_{d\mid n}\phi\left(d\right)$
