Another elementary enumeration

Let \varphi(n);n\in \mathbb{N} denote the number of integers 1\le k\le n such that (k,n)=1 (Euler’s Phi Function). I read a proof of the following fact about the function proved using group theory; indicating the power ofgroup theory in enumerative combinatorics.

\displaystyle\sum_{d|n}\varphi(d)=n

Direct Proof: We shall assume that the reader is aware of the fact that \varphi is multiplicative that is \varphi(p_1^{\alpha_1} \dots p_k^{\alpha_k})=\varphi(p_1^{\alpha_1})\dots \varphi(p_k^{\alpha_k}). We know that \varphi(p^k)=p^k-p^{k-1}. Let m=p^k, then

\displaystyle\sum_{d|m}\varphi(d)=1+\sum_{t=1}^{k}p^t-p^{t-1}=p^k

Considering the general case where n=p_1^{\alpha_1}\dots p_k^{\alpha_k},

\displaystyle \sum_{d|n}\varphi(d)=\sum_{d|n}\varphi\left( p_1^{\beta_1}\dots p_k^{\beta_n} \right) for every \beta_i\le \alpha_i;1\le i \le k.

\displaystyle \sum_{d|n}\varphi(n)=\sum_{\beta_1=0}^{\alpha_1} \dots\sum_{\beta_n=0}^{\alpha_n}\varphi(p_1^{\beta_1}) \dots \varphi(p_n^{\beta_n})

\displaystyle\sum_{d|n}\varphi(n)=\prod_{i=1}^{k}\sum_{\beta_i=0}^{\alpha_i}\varphi(p_i^{\beta_i})=n

 

Here is a simpler looking group theoretic proof.

There are exactly \varphi(d) generators of the subgroup \mathbb{Z}_d where d is a divisor of n. Every element of \mathbb{Z}_n is a generator of exactly one subgroup of \mathbb{Z}_d.

Advertisements

ನಿಮ್ಮದೊಂದು ಉತ್ತರ

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