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

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

Let . For each divisor of , let us count the number of elements with . When , this is just . What about when ? If is odd then clearly there is no such . Otherwise, implies that and must both be even. Moreover, this happens iff . Hence, as before, the number of such is .

This works in general: for any , the number of elements such that is . So summing over all , which is the same as summing over all , gives the total number of elements of , which is . 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!)

### Like this:

Like Loading...

*Related*

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.

Here is a link for the solution in .pdf format.

http://tiny.cc/16s4zx

I’m sorry. This is the link for the proof:

http://tiny.cc/2it4zx

Very interesting! Btw to write in LaTeX on WP: https://en.support.wordpress.com/latex/ And although \begin{align}\end{align} doesn’t work, \begin{aligned}\end{aligned} does.