# Proof of a well-known identity involving Euler’s phi function

Let $\phi(n)$ be Euler’s function, i.e., the number of positive integers not exceeding $n$ that are coprime to $n$. A famous identity goes as follows:

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

where the sum is taken over all positive divisors of $n$. Here is a counting argument for a proof.

Let $S=\{1,\dots,n\}$. For each divisor $d$ of $n$, let us count the number of elements $m\in S$ with $\gcd(m,n)=d$. When $d=1$, this is just $\phi(n)$. What about when $d=2$? If $n$ is odd then clearly there is no such $m$. Otherwise, $\gcd(m,n)=2$ implies that $m$ and $n$ must both be even. Moreover, this happens iff $\gcd(m/2,n/2)=1$. Hence, as before, the number of such $m$ is $\phi(n/2)$.

This works in general: for any $d\mid n$, the number of elements $m\in S$ such that $\gcd(m,n)=d$ is $\phi(n/d)$. So summing $\phi(n/d)$ over all $d\mid n$, which is the same as summing $\phi(d)$ over all $d\mid n$, gives the total number of elements of $S$, which is $n$. This proves the desired result.

This begs for a generalisation. I will add it here when I come up with one. (I really need to sleep now!)

Filed under Combinatorics, Number theory

### 4 responses to “Proof of a well-known identity involving Euler’s phi function”

1. I have a generalization.

Generalization:

I claim that

$\displaystyle\sum_{d \mid N} \phi_n(d) =\begin{cases} \frac{N}{n},&\mbox{if } n\mid N \\ 0,&\mbox{if } n\nmid N. \end{cases}$

where $\phi_n(N) = |\{k\in\mathbb{{N}} : k\leqN \text{ and gcd}(k,N)=n\}|$

Lemma:
$\phi_n(d) = \begin{cases}\phi(\frac{d}{n}),&\mbox{if } n\mid d \\ 0,&\mbox{if } n\nmid d . \end{cases}$

Proof:

Case-i: $n \nmid d$

It is trivial that $\text{gcd}(d,k) \neq n \forall k\in \mathbb{{Z}}$.
So, $\phi_n(d) = 0$

Case-ii: $n\mid d$

Let $d = an$

Let $\text{gcd}(d,k) = n \text{ for some } k\in\mathbb{{N}}$.
Then, $n\nmid k$. Let $k = bn$.

Therefore, $\text{gcd}(d,k) = n \iff n\times\text{gcd}(a,b) = n \iff \text{gcd}(a,b) = 1$

So, $\phi_n(d) = |\{k\in\mathbb{{d}} : k\leq d \text{ and gcd}(k,d)=n\}|$
$= |\{bn\in\mathbb{{N}} : bn\leq an \text{ and gcd}(bn,an)=n\}|$
$= |\{b\in\mathbb{{N}} : b\leq a \text{ and gcd}(b,a)=1\}|$
$=\phi(a)$
$=\phi(\frac{d}{n})$

Now,if $d$ is a divisor of $n$, $n \nmid N \Rightarrow n\nmid d$.
So, if $n \nmid N$, $\displaystyle\sum_{d \mid N} \phi_n(d) = \displaystyle\sum_{d \mid N} 0 = 0$.

And if,
$n \mid N$, then $\displaystyle\sum_{d \mid N} \phi_n(d)$
$= \displaystyle\sum_{d \mid N \text{ and }n\mid d} \phi_n(d) + \displaystyle\sum_{d \mid N \text{ and }n\nmid d} \phi_n(d)$
$= \displaystyle\sum_{d \mid N \text{ and }n\mid d} \phi_n(d) + 0$
$= \displaystyle\sum_{d \mid N \text{ and }n\mid d} \phi_n(d)$
$= \displaystyle\sum_{\frac{d}{n} \mid \frac{N}{n} } \phi_n(d)$
$= \displaystyle\sum_{\frac{d}{n} \mid \frac{N}{n} } \phi(\frac{d}{n})$
$=\displaystyle\sum_{d \mid \frac{N}{n} } \phi(d) = \frac{N}{n}$

This completes the proof.