# Thread: Summation of Euler's φ-Function

1. ## 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.

2. 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

3. Let $\displaystyle G$ be a cyclic group of order $\displaystyle n$ and $\displaystyle a$ be the generator .

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

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

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

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

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

Note that $\displaystyle d$ is any divisor of $\displaystyle n$ and each element in the group must have its order , by equating the number of elements we obtain $\displaystyle \displaystyle {n = \sum_{d|n} \phi(d)}$

4. One more proof:

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

If $\displaystyle n=1$

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

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

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

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

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

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

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

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

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

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

Hence:

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

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