A Combinatorial Proof of a Formula Involving Euler’s Totient Function

Several years ago I found a proof of the following identity, which I had not seen before (and still haven’t seen anywhere else):

\displaystyle \sum_{k=1}^n \left\lfloor \frac{n}{k} \right\rfloor \varphi(k) = \frac{n(n+1)}{2},

where \varphi(n) is Euler’s totient function, the number of positive integers less than or equal to n and relatively prime to n.

Over a year ago I asked for additional proofs of this identity on Math Stack Exchange and got some nice ones.  My favorite, though, is a combinatorial proof that I managed to come up with after I had asked the question.  (It was a modification of one of my original proofs.)

Proof: Both sides count the number of fractions (reducible or irreducible) in the interval (0,1] with denominator n or smaller.

Right side: the number of ways to pick a numerator and a denominator is the number of ways to choose two numbers with replacement from the set \{1, 2, \ldots, n\}.  This is known to be
\displaystyle \binom{n+2-1}{2} = \frac{n(n+1)}{2}.

Left side: The number of irreducible fractions in (0,1] with denominator k is equal to the number of positive integers less than or equal to k and relatively prime to k; i.e., \varphi(k).  For a given irreducible fraction \frac{a}{k}, there are \left\lfloor \frac{n}{k} \right\rfloor total fractions with denominators n or smaller in its equivalence class.  (For example, if n = 20 and \frac{a}{k} = \frac{1}{6}, then the fractions \frac{1}{6}, \frac{2}{12}, and \frac{3}{18} are those in its equivalence class.)  Thus the sum
\displaystyle \sum_{k=1}^n \left\lfloor\frac{n}{k} \right\rfloor \varphi (k)
also gives the desired quantity.

Advertisements
This entry was posted in combinatorics, elementary number theory. Bookmark the permalink.

2 Responses to A Combinatorial Proof of a Formula Involving Euler’s Totient Function

  1. Eric Naslund says:

    This identity comes from the more general setting of summing a multiplicative function convoluted with the constant function, that is 1*f(n)=\sum_{d|n} f(d) where * represents Dirichlet convolution. Looking at the sum \sum_{n\leq x}1*f(n)=\sum_{n\leq x}\sum_{d|n} f(d), we see that by switching the order of summation, the above equals \sum_{d\leq x} f(d)\sum_{n\leq x:\ d|n}1=\sum_{d\leq x} f(d) \left[\frac{x}{d}\right]. Since \sum_{d|n}\phi(d)=n, and \sum_{n\leq x} n =\frac{x(x+1)}{2}, we recover your identity \frac{x(x+1)}{2}=\sum_{n\leq x }\phi(n) \left[\frac{x}{n}\right].

    **fixed typos. Please delete other comment..

  2. mzspivey says:

    Thanks, Eric. Aryabhata’s answer on my math.SE question about this identity uses the same idea of switching the order of summation, but it does not place that in the more general context of Dirichlet convolution.

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