# Euler's totient function Proof

• Mar 9th 2011, 12:17 AM
demode
Euler's totient function Proof
Where $\displaystyle n$ is an integer and $\displaystyle d$ is a positive divisor of n and $\displaystyle \phi$ is the Euler Totient function, how do we prove that:

$\displaystyle \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.
• Mar 9th 2011, 01:11 AM
chisigma
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 \displaystyle g(n)= \sum_{d|n} f(d)$

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

Here $\displaystyle \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 \displaystyle \varphi(n)= \sum_{d|n} \mu(d)\ \frac{n}{d} \implies n= \sum_{d|n} \varphi (d)$ (2)

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$
• Mar 9th 2011, 02:19 AM
Shanks
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 $\displaystyle \{k|(n,k)=d\}$ where d divides n, forms a partition of {1,2,...,3}. for each d, the subset $\displaystyle \{k|(n,k)=d\}$ contains $\displaystyle \phi(n/d)$ elements.
as d run over all divisors of n, n/d run over all divisors of n, the identity follows.
• Mar 9th 2011, 02:34 AM
tonio
Quote:

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

$\displaystyle \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 $\displaystyle 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 $\displaystyle \phi(k)$ generators.

Put the above together and voila!

Tonio
• Mar 9th 2011, 07:44 PM
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 $\displaystyle \{ k| gcd(k,n)=d \}$?
• Mar 10th 2011, 05:30 AM
Shanks
Quote:

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 $\displaystyle \{ 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 $\displaystyle \{ k| gcd(k,n)=d \}$ equals to the cardinality of the set $\displaystyle \{ k| gcd(k/d,n/d)=1 \}$, that is $\displaystyle \phi(n/d)$.