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

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

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 with denominator 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 . This is known to be

*Left side:* The number of irreducible fractions in with denominator is equal to the number of positive integers less than or equal to and relatively prime to ; i.e., . For a given irreducible fraction , there are total fractions with denominators or smaller in its equivalence class. (For example, if and , then the fractions , and are those in its equivalence class.) Thus the sum

also gives the desired quantity.

This identity comes from the more general setting of summing a multiplicative function convoluted with the constant function, that is where * represents Dirichlet convolution. Looking at the sum , we see that by switching the order of summation, the above equals . Since , and , we recover your identity .

**fixed typos. Please delete other comment..

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.