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!)

Advertisements

4 Comments

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s