Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

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.

share|improve this question
    
What immediately jumps out is how such a complicated function like the totient function has an identity involving the simple summation of integers 1 to n. Seems like a good way to prove it is to show that the expression inside the sum is a "rearrangement" of the sequence of integers 1 to n –  crasic Oct 27 '10 at 5:42

4 Answers 4

up vote 23 down vote accepted

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.

share|improve this answer
    
Nice. Interchanging the order of summation is always a good idea, but it's one I didn't think of here. –  Mike Spivey Oct 27 '10 at 16:45

In case anyone is interested, here are the full versions of my two proofs. (I constructed the combinatorial one from my original partially combinatorial one after I posted the question.)


The non-combinatorial proof

As Derek Jennings observes, $\lfloor \frac{n+1}{k} \rfloor - \lfloor \frac{n}{k} \rfloor$ is $1$ if $k|(n+1)$ and $0$ otherwise. Thus, if $$f(n) = \sum_{k=1}^n \left\lfloor\frac{n}{k} \right\rfloor \varphi (k),$$ then $$\Delta f(n) = f(n+1) - f(n) = \sum_{k|(n+1)} \phi(k) = n+1,$$ where the last equality follows from the well-known formula Aryabhata cites.

Then $$\sum_{k=1}^n \left\lfloor\frac{n}{k} \right\rfloor \varphi (k) = f(n) = \sum_{k=0}^{n-1} \Delta f(k) = \sum_{k=0}^{n-1} (k+1) = \frac{n(n+1)}{2}.$$


The combinatorial proof

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

For the 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 $$\binom{n+2-1}{2} = \frac{n(n+1)}{2}.$$

Now for the 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)$. Then, 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 $$\sum_{k=1}^n \left\lfloor\frac{n}{k} \right\rfloor \varphi (k)$$ also gives the desired quantity.

share|improve this answer

Look at the problem of counting all the triples (d,m+1,k) where $d\leq m\leq n$ and $gcd(d,m)=\frac{m}{k}$. For each (d,m+1) we have exactly one k such that $gcd(d,m)=\frac{m}{k}$, and so we are counting exactly all the pairs (i,j) where $ i < j \leq n+1 $ which is $\binom{n+1}{2}$.

On the other hand, for each k , if $ gcd(d,m)=\frac{m}{k} $, then $ k \mid m $ and there are $ \left\lfloor \frac{n}{k}\right\rfloor $ such m's, and for each m we have $\varphi(k)$ d's that satisfies this equality, so there are $ \left\lfloor \frac{n}{k}\right\rfloor \varphi(k) $ triples that end with k.


The idea is counting the number of ways to choose two numbers from 1,2,...,n+1 (which is the right side of the equation). Once you choose the larger number m+1, you have m options which is exactly $\sum_{d\mid m} \varphi(d)$ (this is basically what Moron wrote). What I wanted to do is to change the counting according to the "relation" between d and m, and the one that worked out is that $\frac{m}{gcd(d,m)}=k$.

So, going over triples (d,m+1,k) where $\frac{m}{gcd(d,m)}=k$ and $d\leq m\leq n$ just mean that (d,m+1) is an ordered pair from {1,...,n} and k is decided as above.

On the other hand, for specific k, if $\frac{m}{gcd(d,m)}=k$ then $k \mid m$ and there are $ \left\lfloor \frac{n}{k}\right\rfloor$ such m's. For each m, if $gcd(d,m)=m/k$ then $gcd(\frac{d}{m/k},\frac{m}{m/k})=gcd(\frac{d}{m}k,k)=1$ and there are $\varphi(k)$ such d's (because $d\leq m$).

So, or each k there are $ \left\lfloor \frac{n}{k}\right\rfloor \varphi(k) $ options , and summing over k will give the left side of the equation.

share|improve this answer
    
Your proof looks interesting, but I'm having trouble following it. For my sake, would you mind filling in some of the details? –  Mike Spivey Oct 27 '10 at 17:01
    
Thanks for the additional detail. –  Mike Spivey Oct 28 '10 at 12:40

We can use induction.

We have $ \lfloor (n+1)/k \rfloor - \lfloor n/k \rfloor = 1 $ when $n \equiv -1 \textrm{ mod } k,$ (for $k>1$) and $0$ otherwise. Hence

$$ \phi(1) + \sum_{k=2}^n \left( \left\lfloor \frac{n+1}{k} \right\rfloor -
\left\lfloor \frac{n}{k} \right\rfloor \right) \phi(k) = \sum_{k=1, k \textrm{ s.t. } n \equiv -1 \textrm{ mod } k}^n \phi(k)$$ $$= \sum_{ k | (n+1), k \ne n+1} \phi(k) = (n+1) - \phi(n+1),$$

using $\sum_{d|k} \phi(d) = k.$ So assuming the result is true for $n,$ we have

$$\sum_{k=1}^{n+1} \left\lfloor \frac{n+1}{k} \right\rfloor \phi(k) = \phi(n+1) + \sum_{k=1}^n \left( \left\lfloor \frac{n+1}{k} \right\rfloor -
\left\lfloor \frac{n}{k} \right\rfloor \right) \phi(k) + \frac{n(n+1)}{2}$$

$$= \phi(n+1) + \phi(1) + \sum_{k=2}^n \left( \left\lfloor \frac{n+1}{k} \right\rfloor -
\left\lfloor \frac{n}{k} \right\rfloor \right) \phi(k) + \frac{n(n+1)}{2},$$

which, using the previous result to substitute for the summation,

$$= (n+1) + \frac{n(n+1)}{2} = \frac{(n+1)(n+2)}{2}.$$

Noting that the result is true when $n=1 \textrm{ and } 2$ completes the proof.

share|improve this answer
    
Induction would not be my first choice; Moron's proof is more natural. But since we're after any proofs... –  Derek Jennings Oct 27 '10 at 9:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.