Math Help - Euler's totient function Proof

1. Euler's totient function Proof

Where $n$ is an integer and $d$ is a positive divisor of n and $\phi$ is the Euler Totient function, how do we prove that:

$\sum_{d|n} \phi(d) = n$ ?

I have absolutely no idea how to approach this problem, any help to get me started is very much appreciated.

2. The 'direct proof' is a little 'efforts spending'. A confortable alternative is to read...

Möbius Inversion Formula -- from Wolfram MathWorld

...where the 'Moebius inversion pair formula' is illustrated...

$\displaystyle g(n)= \sum_{d|n} f(d)$

$\displaystyle f(n)= \sum_{d|n} \mu(d)\ g(\frac{n}{d})$ (1)

Here $\mu(*)$ is the 'Moebius function'. Of course the (1) can be apply 'from top to bottom' or 'from bottom to top'... using the last option You derive that...

$\displaystyle \varphi(n)= \sum_{d|n} \mu(d)\ \frac{n}{d} \implies n= \sum_{d|n} \varphi (d)$ (2)

Kind regards

$\chi$ $\sigma$

3. chisigma has provided a "advanced" proof, here is a "elementary" proof:
consider the set {1,2,3,...,n}, there are n elements in it, for each element k , there is exactly one divisor d of n such that (n,k)=d. so the collection of all subsets $\{k|(n,k)=d\}$ where d divides n, forms a partition of {1,2,...,3}. for each d, the subset $\{k|(n,k)=d\}$ contains $\phi(n/d)$ elements.
as d run over all divisors of n, n/d run over all divisors of n, the identity follows.

4. Originally Posted by demode
Where $n$ is an integer and $d$ is a positive divisor of n and $\phi$ is the Euler Totient function, how do we prove that:

$\sum_{d|n} \phi(d) = n$ ?

I have absolutely no idea how to approach this problem, any help to get me started is very much appreciated.

An alternative idea to the two already given, if you know some group theory:

Look at the cyclic group $C_n$ of order n , and then use that :

1) It has a unique (cyclic, also) group of order d, for any divisor d of n ;

2) A cyclic group of order k has exactly $\phi(k)$ generators.

Put the above together and voila!

Tonio

5. Thanks Tonio and Shanks. I know group theory so Tonio's suggestion was also pretty straightforward. Also as a related question, how should I go about calculating the cardinality of the set $\{ k| gcd(k,n)=d \}$?

6. Originally Posted by demode
Thanks Tonio and Shanks. I know group theory so Tonio's suggestion was also pretty straightforward. Also as a related question, how should I go about calculating the cardinality of the set $\{ k| gcd(k,n)=d \}$?
gcd(k,n)=d implies
(1) k and n are both divisible by d;
(2) k/d and n/d are relatively prime.
so combine (1) and (2), we have
the cardinality of the set $\{ k| gcd(k,n)=d \}$ equals to the cardinality of the set $\{ k| gcd(k/d,n/d)=1 \}$, that is $\phi(n/d)$.