Funciones Aritméticas

Teoría

Las funciones aritméticas son funciones que defines sobre el conjunto de los enteros positivos. Normalmente van a los números complejos, aunque en las olimpiadas de matemáticas, el codominio casi siempre es de enteros o números reales. El concepto central en este tema es la multiplicatividad. Dices que una función aritmética $f$ es multiplicativa si $f(mn) = f(m)f(n)$ siempre que $\gcd(m, n) = 1$. Si la igualdad se cumple para todos los $m, n$, la función es completamente multiplicativa. Esta propiedad es súper poderosa porque el Teorema Fundamental de la Aritmética te permite evaluar una función multiplicativa para cualquier entero $n$ con solo conocer sus valores en las potencias de primos. Si $n = p_1^{e_1} \cdots p_k^{e_k}$, entonces $f(n) = f(p_1^{e_1}) \cdots f(p_k^{e_k})$.

Estas funciones son herramientas fundamentales en teoría de números y las vas a encontrar seguido en problemas de divisibilidad, conteo y aritmética modular. Los ejemplos más conocidos son la función phi de Euler $\phi(n)$ (que cuenta los enteros coprimos con $n$), las funciones de divisores $\tau(n)$ y $\sigma(n)$ (que cuentan y suman los divisores), y la función de Möbius $\mu(n)$. En competencias avanzadas como el A