# Identity involving Euler’s totient function: n∑k=1⌊nk⌋φ(k)=n(n+1)2\sum \limits_{k=1}^n \left\lfloor \frac{n}{k} \right\rfloor \varphi(k) = \frac{n(n+1)}{2}

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

Challenge: Prove

I have two proofs, one of which is partially combinatorial.

I’m posing this problem partly because I think some folks on this site would be interested in working on it and partly because I would like to see a purely combinatorial proof. (But please post any proofs; I would be interested in noncombinatorial ones, too. I’ve learned a lot on this site by reading alternative proofs of results I already know.)

I’ll wait a few days to give others a chance to respond before posting my proofs.

EDIT: The two proofs in full are now given among the answers.

One approach is to use the formula $\displaystyle \sum_{d \mid k} \varphi(d) = k$

So we have that $\displaystyle \sum_{k=1}^{n} \sum_{d \mid k} \varphi(d) = n(n+1)/2$

Exchanging the order of summation we see that the $\displaystyle \varphi(d)$ term appears $\displaystyle \left\lfloor \frac{n}{d} \right\rfloor$ times

and thus

$\displaystyle \sum_{d=1}^{n} \left\lfloor \frac{n}{d} \right\rfloor \varphi(d) = n(n+1)/2$

Or in other words, if we have the $n \times n$ matrix $A$ such that

$\displaystyle A[i,j] = \varphi(j)$ if $j \mid i$ and $0$ otherwise.

The sum of elements in row $i$ is $i$.

The sum of elements in column $j$ is $\displaystyle \left\lfloor \frac{n}{j} \right\rfloor \varphi(j)$ and the identity just says the total sum by summing the rows is same as the total sum by summing the columns.