φ, τ y σ son multiplicativas.
En teoría de números, dices que una función aritmética $f(n)$ es multiplicativa si $f(mn) = f(m)f(n)$ siempre que $\gcd(m, n) = 1$. Esta propiedad es súper poderosa porque el Fundamental Theorem of Arithmetic te permite descomponer cualquier entero $n > 1$ en un producto único de potencias de primos $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$. Por lo tanto, si una función es multiplicativa, para calcular su valor en cualquier entero solo tienes que calcular su valor para potencias de primos: $$f(n) = f(p_1^{e_1}) f(p_2^{e_2}) \cdots f(p_k^{e_k}).$$
Las tres funciones multiplicativas más comunes e importantes que aparecen en competencias como el AIME y la USAMO son la Euler's totient function ($\varphi$), la función de cantidad de divisores ($\tau$ o $d$) y la función de suma de divisores ($\sigma$). Estas funciones describen propiedades fundamentales de los divisores de un entero y su relación con la aritmética modular. Si dominas estas funciones, vas a poder resolver problemas complejos que involucran sumas de divisores, inversos modulares y grupos cíclicos, dividiendo el problema en componentes independientes basados en la factorización de primos.
Una idea clave cuando trabajas con estas funciones es