Prueba: $\phi(n)=\sum\limits_{k=1}^{n-1} \left\lfloor\frac{1}{\operatorname{gcd}(n,k)} \right\rfloor$

Question

Tengo una pregunta ¿como iniciar la prueba de la siguiente tarea:

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

Alguna pista de por dónde y cómo empezar? Sé que la definición de

$$\phi(n):=\sum_{\substack{m=1\\(m,n)=1}}^n 1$ $ , pero no sé cómo moverse en el. Cualquier ayuda sería bien.

Saludos.

Answer 1

A menudo es una buena idea para ampliar la distribución de cantidades a ver si esto le ayuda a entender lo que está pasando:

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

donde estoy escribiendo $ (n,k) $ como abreviación $ \mbox{gcd}(n,k)$.

Un par de cosas en las que pensar:

1. ¿Cuál es el menor valor posible de $ (n,k) $? ¿Cuál es el mayor? ¿Cuáles son los posibles valores de $ \left\lfloor \frac{1}{(n,k)}\right\rfloor $? Cuando estos valores se producen?

2. ¿Qué $ \phi(n) $ decirle a usted acerca de $n$?