Problema de Euler del Phi de la función

Question

Deje $S(n)$ $S(n)=\left\{k\;\left|\;\left\{\frac{n}{k}\right\}\right.\geq \frac{1}{2}\right\}$donde $\{x\}$ es la parte fraccionaria de $x$

Probar que :

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

tal vez el hecho de \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}

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

puede ayudar, pero no puedo probar estas dos ecuaciones

---

Editado:lo Siento que mi pregunta es para probar que los dos ecuaciones antes, porque ya he conocido ¿cómo se relacionan el problema con estas dos ecuaciones, y también he conocido cómo probar la segunda ecuación a partir de la Identidad que involucra Euler totient función: $\sum \limits_{k=1}^n \left\lfloor \frac{n}{k} \right\rfloor \varphi(k) = \frac{n(n+1)}{2}$ pero no puedo resolver el primero con el método similar.

Answer 1

Voy a recordar (como es más o menos lo indicado en el enlace que se proporciona) que para la segunda identidad $$ \sum_{0<k\leq 2n}\left\lfloor\frac nk\right\rfloor \varphi(k)=\frac{n^2+n}2 $$ ambos lados pueden ser interpretados como el conteo de los enteros pares de $(x,y)$ satifying $0\leq x<y\leq n$ como sigue. El lado derecho cuenta con un valor fijo de $y$, dando $1+2+\cdots+n=\frac{n(n+1)}2$. El lado izquierdo (donde claramente sólo los valores de $k\leq n$ contribuir) cuenta por el valor de $k=y/\gcd(x,y)$, en otras palabras por el denominador de la fracción $x/y$ después de la reducción de la misma. Para tal $k$ hay $\phi(k)$ posibles valores de $l=x/\gcd(x,y)$ (el numerador correspondiente), y para los que recibieron $(l,k)$ el número de pares de $(x,y)$ que reducir a es igual al número de múltiplos de $k$ que${}\leq n$,$\lfloor\frac nk\rfloor$.

Ahora la identidad de la primera se puede hacer una ligera variación de este. El punto crucial es interpretar $\lfloor\frac nk+\frac12\rfloor$ como el número de impares múltiplos de $k$ que${}\leq2n$, que es fácilmente controlado. Esto nos lleva a contar de enteros pares de $(x,y)$ satifying $0\leq x<y\leq2n$ y no tanto incluso. Contando con la fijación $y$, se obtiene la combinación de los valores impares de $y$ la contribución $1+3+5+\cdots+(2n-1)=n^2$, y la combinación de los incluso los valores de $y$ la contribución $1+2+3+\cdots+n=\frac{n(n+1)}2$, en total $\frac{3n^2+n}2$ que es la mano derecha de su primera identidad. Para el lado izquierdo, el argumento es exactamente igual que antes: la reducción de par $(l,k)$ no puede tener ambos componentes, incluso, para cada $k$ da el mismo número $\phi(k)$ de reducción de los pares como antes, sin embargo, podemos tomar sólo impares múltiplos de cualquier reducción de par, dando a $\lfloor\frac nk+\frac12\rfloor\phi(k)$ contribuciones de un determinado $k$ (para este caso los valores de $n<k\leq2n$ lo aportan).

Como usted probablemente ya había observado, uno ha $\lfloor\frac nk+\frac12\rfloor-\lfloor\frac nk\rfloor=1$ si $k\in S(n)$ y la diferencia es $0$ lo contrario, que conduce fácilmente a su resultado inicial.

Answer 2

Por inducción. El uso que

$$ \sum_{k \a mediados n} \varphi(k) = n $$

y

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

Mirando con cuidado la diferencia entre el $S(n)$ $S(n+1)$ le da:

$$ \sum_{k \in S(n+1)} \varphi(k) = \sum_{k \in S(n)} \varphi(k) + \sum_{k \a mediados de 2n + 1}\varphi(k) + \sum_{\substack{k \a mediados de n + 1 \\ (n+1)/k \textrm{ impar}}} \varphi(2k) - \sum_{k \a mediados de n+1} \varphi(k)\\ = (n+1)^2 + \sum_{\substack{k \a mediados de n + 1 \\ (n+1)/k \textrm{ impar}}} \varphi(2k) - n - 1. $$

Escribir $n + 1= 2^a m$ $a \geq 0$ $m$ impar. A continuación, la suma restante es

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