# Summation of Euler's φ-Function

• Jul 7th 2010, 12:45 PM
elemental
Summation of Euler's φ-Function
Euler's φ-function measures the number of positive integers equal to or less than n,
which are relatively prime to n.
Compute the following:
∑ φ(d)
d|n

Prove this is correct.

The only observation I've made so far is that this must be a multiplicative function.
• Jul 7th 2010, 01:00 PM
chiph588@
Quote:

Originally Posted by elemental
Euler's φ-function measures the number of positive integers equal to or less than n,
which are relatively prime to n.
Compute the following:
∑ φ(d)
d|n

Prove this is correct.

The only observation I've made so far is that this must be a multiplicative function.

http://www.mathhelpforum.com/math-he...tml#post519966
• Jul 7th 2010, 11:54 PM
simplependulum
Let $G$ be a cyclic group of order $n$ and $a$ be the generator .

We have exactly $a^n = 1$ , by Lagrange's Theorem , we know $o(b) | n$ . We now show that for a given order $d|n$ , the number of elements in $G$ of this order is $\phi(d)$ :

Suppose $o(b) = d$ , then $b^d = 1$ and since it is a cyclic group , let $b = a^m$ , so $a^{md} = 1$ and $md = nk$

$m = \frac{kn}{d}$ we have $(k,d) = 1$ , otherwise $(a^m)^{d/(k,d)} = 1$ thus $o(b) \neq d$ .

Moreover , to avoid repetition , let $k < d$ because if $k > d$ , by writing $k = dq + k'$ we can show that $a^{kn/d} = a^{k'n/d}$ where $0 < k' < d$ .

Therefore , the number of elements of order $d$ is the number of numbers not exceeding $d$ and prime to it : $\phi(d)$

Note that $d$ is any divisor of $n$ and each element in the group must have its order , by equating the number of elements we obtain $\displaystyle {n = \sum_{d|n} \phi(d)}$
• Jul 8th 2010, 12:22 AM
Also sprach Zarathustra
One more proof:

We use the fact that $\phi$ is multiplicative function.

If $n=1$

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

If $n>1$, we look on the following function:

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

since $\phi$ is multiplicative function, easily prooved that also $F$ is multiplicative function.

Let $n={p_1^{k_1}}{p_2^{k_2}}...{p_s^{k_s}}$

so, $F(n)=F({p_1^{k_1}})F({p_2^{k_2}})...F({p_s^{k_s}})$

for every $i=1,2,...,s$

$F({p_i^{k_i}})=\sum_{d|{p_i^{k_i}}} \phi(d)$

$=\phi(1)+\phi(p_i)+\phi(p^2_i)+...+\phi(p_i^{k_i})$

$=1+(p_i-1)+(p^2_i-1)+...+(p_i^{k_i}-p_i^{k_{i-1}})=p_i^{k_i}$

Hence:

$F(n)={p_1^{k_1}}{p_2^{k_2}}...{p_s^{k_s}}=n$

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