Funciones Multiplicativas y sus aplicaciones olimpicas

Una función $f$ es multiplicativa si $f(mn) = f(m)f(n)$ cuando $m$ y $n$ son primos relativos. Ejemplos clásicos de funciones multiplicativas son $\tau(n)$ (número de divisores de $n$), $\phi(n)$ (número de números menores a $n$ que son primos relativos de $n$), $\sigma(n)$ (la suma de los divisores de $n$). Una de las cosas más útiles de una función multiplicativa, es que muchas veces se reduce a estudiar que pasa con las potencias de primos. Por ejemplo, si uno quiere sacar una fórmula para $\phi$, basta saber que pasa con una potencia de primo, y la multiplicatividad lo extiende a $n$ arbitrario. Por eso si $n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$ entonces $\phi(n) = p_1^{\alpha_1-1}(p_1-1) p_2^{\alpha_2-1}(p_2-1)\cdots p_k^{\alpha_k-1} (p_k -1)$.

Un teorema muy útil en la teoría de funciones multiplicativas es el siguiente (y los invito a demostrarlo): Si $f$ es una función multiplicativa, entonces $g(n) = \sum_{d | n} f(d)$ también es multiplicativa.

Un teorema un poco más general es: Si $f$ es multiplicativa y $g$ es multiplicativa entonces $$h(n) = \sum_{d | n} f(d)g\left(\frac{n}{d}\right)$$ también es multiplicativa.

Aquí les va una aplicación clásica del teorema:
Demostraré que $$\sum_{d| n} \phi(d) = n.$$ Este resultado tiene muchas demostraciones muy bonitas. La siguiente es una demostración fea, pero fácil:

$\phi$ es multiplicativa, por lo tanto $$g(n) = \sum_{d|n} \phi(d)$$ es multiplicativa. Por lo tanto basta saber que pasa con las potencias de primos. Veamos que pasa: $$g(p^{\alpha}) = \sum_{d | p^{\alpha}} \phi(d) = \phi(1) + \phi(p) + \phi(p^2) + \ldots + \phi(p^{\alpha})$$ $$= 1 + (p-1) + (p-1)p + (p-1)p^2 + \ldots + (p-1)p^{\alpha-1}$$ $$= 1+ (p-1) (1 + p + \ldots + p^{\alpha-1}) = 1 + (p-1) \frac{p^{\alpha} - 1}{p-1} = 1 + (p^{\alpha} - 1) = p^{\alpha}.$$ Entonces $g$ es multiplicativa y $g(p^{\alpha}) = p^{\alpha}$, por lo tanto $g(n) = n$.

Un problema para ilustrar la idea de usar funciones multiplicativas es el siguiente:

Sea $\tau(n)$ el número de divisores de $n$ y $\omega(n)$ el número de divisores primos (distintos) de $n$ (por ejemplo $\omega(8) = 1, \omega(30) = 3$). Demuestra que $$\tau(n^2) = \sum_{d|n} 2^{\omega(d)}.$$ Para los curiosos que quieren una demostración que no usa "multiplicabilidad", aquí tengo una solución en inglés que encuentra una biyección entre los divisores de $n^2$ y los cuates de $2^{\omega(d)}$.