# Problem on Euler's Phi function

Let $S(n)$ be $S(n)=\left\{k\;\left|\;\left\{\frac{n}{k}\right\}\right.\geq \frac{1}{2}\right\}$,where $\{x\}$ is the fractional part of $x$

Prove that :

\begin{align} \sum_{k\in S(n)} \varphi(k)=n^2 \end{align}

maybe the fact \begin{align} \sum_{k \leq 2n}\left\lfloor{\frac{n}{k}+\frac{1}{2}}\right\rfloor \varphi(k)=\frac{3n^2+n}{2}\end{align}

and \begin{align} \sum_{k \leq 2n}\left\lfloor{\frac{n}{k}}\right\rfloor \varphi(k)=\frac{n^2+n}{2}\end{align}

can help, but I can't prove these two equations

Edited:Sorry that my question is to prove the two equation before, because I've already known how to relate the problem with these two equations, and I've also known how to prove the second equation from Identity involving Euler's totient function: $\sum \limits_{k=1}^n \left\lfloor \frac{n}{k} \right\rfloor \varphi(k) = \frac{n(n+1)}{2}$ but I can't solve the first one with the similar method.

-
For $n=2,3$ I get repectively $S(n)=\{3\},\{4,5\}$ and the summation of $\phi(k)$ gives $2,6$, which is not what your claim says. If I replace the condition by${}\geq\frac12$, then $S(n)=\{3,4\},\{2,4,5,6\}$ and the sums are $4,9$ as they should. Was the question supposed to have $S(n)=\left\{k\mid\left\{\frac{n}{k}\right\}\geq\frac{1}{2}\right\}$? –  Marc van Leeuwen Jul 8 '12 at 6:52
@ Marc van Leeuwen,Oh yes, sorry I mistype the question –  Golbez Jul 8 '12 at 6:59
@Golbez: Treating the question as a sort of reply to comments makes it hard to understand. It appears the "sorry" is a response to Eric's answer; it belongs to your comment to that answer and shouldn't appear out of context in the question, where it's confusing. –  joriki Jul 8 '12 at 7:27

By induction. Use that

$$\sum_{k \mid n} \varphi(k) = n$$

and

$$\varphi(2k) = \begin{cases} 2\varphi(k) & \textrm{if } k \textrm{ is even}\\ \varphi(k) & \textrm{if } k \textrm{ is odd} \end{cases}$$

Carefully looking at the difference between $S(n)$ and $S(n+1)$ gives:

$$\sum_{k \in S(n+1)} \varphi(k) = \sum_{k \in S(n)} \varphi(k) + \sum_{k \mid 2n + 1}\varphi(k) + \sum_{\substack{k \mid n + 1 \\ (n+1)/k \textrm{ odd}}} \varphi(2k) - \sum_{k \mid n+1} \varphi(k)\\ = (n+1)^2 + \sum_{\substack{k \mid n + 1 \\ (n+1)/k \textrm{ odd}}} \varphi(2k) - n - 1.$$

Write $n + 1= 2^a m$ with $a \geq 0$ and $m$ odd. Then the remaining sum is

$$\sum_{k \mid m} \varphi(2^{a+1}k) = 2^a \sum_{k \mid m} \varphi(k) = 2^a m = n+1.$$

-
Thank you very much!Awesome!Is there other way to prove the first equation to solve this problem? –  Golbez Jul 8 '12 at 10:28
Of course by the "first" equation OP means the middle one in their question. –  anon Jul 8 '12 at 10:41

I'll recall (as is more or less indicated in the link you provided) that for the second identity $$\sum_{0<k\leq 2n}\left\lfloor\frac nk\right\rfloor \varphi(k)=\frac{n^2+n}2$$ both sides can be interpreted as counting the integer pairs $(x,y)$ satifying $0\leq x<y\leq n$ as follows. The right hand side counts by fixed value of $y$, giving $1+2+\cdots+n=\frac{n(n+1)}2$. The left hand side (where clearly only values $k\leq n$ contribute) counts by the value of $k=y/\gcd(x,y)$, in other words by the denominator of the fraction $x/y$ after reducing it. For such a $k$ there are $\phi(k)$ possible values for $l=x/\gcd(x,y)$ (the corresponding numerator), and for given $(l,k)$ the number of pairs $(x,y)$ that reduce to it is equal to the number of multiples of $k$ that are${}\leq n$, which is $\lfloor\frac nk\rfloor$.

Now the first identity can be done by a slight variation of this. The crucial point is to interpret $\lfloor\frac nk+\frac12\rfloor$ as the number of odd multiples of $k$ that are${}\leq2n$, which is easily checked. This leads us to count integer pairs $(x,y)$ satifying $0\leq x<y\leq2n$ and not both even. Counting by fixing $y$, one gets combining the odd values of $y$ the contribution $1+3+5+\cdots+(2n-1)=n^2$, and combining the even values of $y$ the contribution $1+2+3+\cdots+n=\frac{n(n+1)}2$, all in all $\frac{3n^2+n}2$ which is it right hand side of your first identity. For the left hand side the argument is exactly as before: the reduced pair $(l,k)$ cannot have both components even, so every $k$ gives the same number $\phi(k)$ of reduced pairs as before, however we can take only odd multiples of any reduced pair, giving $\lfloor\frac nk+\frac12\rfloor\phi(k)$ contributions from a given $k$ (for this case values $n<k\leq2n$ do contribute).

As you probably already had observed, one has $\lfloor\frac nk+\frac12\rfloor-\lfloor\frac nk\rfloor=1$ if $k\in S(n)$ and the difference is $0$ otherwise, which easily leads to your initial result.

-
Very understandable proof! Thanks a lot! –  Golbez Jul 8 '12 at 14:25