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.


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


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



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.


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

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s