An identity involving Euler’s totient function

Let \varphi denote Euler’s totient function and let n be a positive integer. Prove that \sum_{d|n} \varphi(d) = n, where d ranges over the positive divisors of n.

Let Z_n = \langle x \rangle denote the (unique) cyclic group of order n. Every element of Z_n generates a unique (cyclic) subgroup, which is cyclic. Recall that Z_n has a unique (cyclic) subgroup of order d for each d|n, and that each of these is generated by \varphi(d) elements. That is, letting G_d denote the set of generators of Z_d, we have Z_n = \bigcup_{d|n} G_d where the union is disjoint. Thus \sum_{d|n} \varphi(d) = n.

Post a comment or leave a trackback: Trackback URL.


Leave a Reply

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

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

%d bloggers like this: