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.