---
tags: number-theory, multiplicative-functions, dirichlet-convolution, mobius-inversion, sieve
---

# Funciones multiplicativas

## Función aritmética
Sea $f : \mathbb{N} \to \mathbb{C}$ una función que va de los naturales a los números complejos. Entonces decimos que $f$ es *aritmética*.

## Función multiplicativa
Sea $f(n)$ una función aritmética. Decimos que $f$ es *multiplicativa* si para dos enteros $m$ y $n$ tales que su $\gcd(m, n) = 1$, entonces $f(mn) = f(m)f(n)$.

Vamos a asumir que $f(1)=1$. Esto se cumple, pues si $f \neq 0$, entonces $f(x) = f(x \cdot 1) = f(x)f(1)$, entonces $f(1)=1$.

## Teorema fundamental de la aritmética
Para un entero positivo $n$, su factorización en primos es única (salvo el orden), y escribimos $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$.

Este teorema es muy útil al evaluar funciones ariméticas multiplicativas, pues si $f$ es multiplicativa, entonces $f(n) = f(p_1^{a_1}) f(p_2^{a_2}) \cdots f(p_k^{a_k})$.

Esto implica que cualquier función multiplicativa queda bien definida únicamente sabiendo su evaluación en potencias de primos.

## Ejemplos de funciones multiplicativas
- Función identidad: $I(n) = n$.
- Función constante: $\textbf{1}(n) = 1$.
- Función potencia: $I_k(n) = n^k$.
- Función identidad multiplicativa:
$$
\epsilon(n) = \begin{cases}
1 & \text{ si $n = 1$} \\
0 & \text{ si $n > 1$}
\end{cases}
$$

Notación: $\displaystyle \sum_{d | n} f(d)$ significa que la suma va a iterar sobre todos los divisores positivos $d$ de $n$.

Ejemplo, $\displaystyle \sum_{d | 6} f(d) = f(1) + f(2) + f(3) + f(6)$.

- Función de divisores: $\displaystyle \sigma_0(n) = \sum_{d | n} 1$. Esta función simplemente devuelve el número de divisores de $n$.
- Función generalizada de divisores: $\displaystyle \sigma_k(n) = \sum_{d | n} d^k$. Esta función devuelve la suma de los divisores de $n$ elevados a la $k$-ésima potencia. En particular, si $k=1$, la función nos devuelve la suma de divisores.
- Función Phi de Euler: $\varphi(n)$. Esta función nos devuelve el número de coprimos con $n$ entre $1$ y $n$. Tratemos de obtener una fórmula para $\varphi(p^a)$. Sabemos que entre los números del $1$ a $p^a$, $p^{a-1}$ son divisibles entre $p$. Por lo tanto $\varphi(p^a) = p^a - p^{a-1} = p^a \left( 1 - \dfrac{1}{p} \right)$.
Por lo tanto, $\varphi(n) = \displaystyle \prod_{i=1}^{k}p_k^{a_k}\left( 1 - \dfrac{1}{p_k} \right) = \prod_{i=1}^{k}p_k^{a_k} \prod_{i=1}^{k} \left( 1 - \dfrac{1}{p_k} \right) = n \prod_{i=1}^{k} \left( 1 - \dfrac{1}{p_k} \right)$.
- Función de Möbius: $\mu(n)$:
$$
\mu(n) = \begin{cases}
1 & \text{ si $n$ es producto de un número par de primos distintos} \\
-1 & \text{ si $n$ es producto de un número impar de primos distintos} \\
0 & \text{ si $n$ tiene algún factor primo repetido}
\end{cases}
$$

Notación:
$$
[cond] = \begin{cases}
1 & \text{ si $cond$ es verdadera}\\
0 & \text{ si $cond$ es falsa}
\end{cases}
$$

Ahora, veamos para cada una de las funciones anteriores, sus evaluaciones cuando $n=p^a$.
- $I(p^a) = p^a$.
- $\textbf{1}(p^a) = 1$.
- $I_k(p^a) = p^{ak}$.
- $\epsilon(p^a) = [p^a==1]$.
- $\sigma_0(p^a) = a+1$. Otra forma de obtener esto es usando la fórmula anterior: $\displaystyle \sigma_0(p^a) = \sum_{d | p^a} 1 = \sum_{i=0}^{a} 1 = a+1$.
- $\displaystyle \sigma_k(p^a) = \sum_{d | p^a} d^k = \sum_{i=0}^{a} (p^i)^k = \sum_{i=0}^{a} (p^k)^i = \dfrac{(p^k)^{a+1} - 1}{p^k - 1}$.
- $\mu(p^a) = -[a==1]$.

En general, cualquier función multiplicativa $f(n)$ se puede expresar como $f(p^a) = g(p, a)$, donde $g$ es cualquier función y $a \geq 1$.

# Convolución de Dirichlet
Sean $f$ y $g$ dos funciones aritméticas. Definimos a la *convolución de Dirichlet* de $f$ con $g$ como:
$$
(f * g)(n) = \sum_{d | n} f(d) g \left( \dfrac{n}{d} \right)
$$

Teorema: si $f$ y $g$ son multiplicativas, entonces $f * g$ también lo es.

Propiedades: sean $f,g,h$ funciones aritméticas y $\alpha, \beta$ constantes. Entonces:
- Conmutativa: $(f * g)(n) = (g * f)(n)$.
- Asociativa: $((f * g) * h)(n) = (f * (g * h))(n)$
- Distributiva: $(f * (\alpha g + \beta h))(n) = (\alpha(f * g) + \beta(f * h))(n)$.

## Ejemplos
- $\displaystyle (f * \epsilon)(n) = \sum_{d | n} f(d) \epsilon \left( \dfrac{n}{d} \right) = f(n)$.
- $\displaystyle (\textbf{1} * \textbf{1})(n) = \sum_{d | n} 1 \cdot 1 = \sum_{d | n} 1 = \sigma_0(n)$.
- $\displaystyle (I_k * \textbf{1})(n) = \sum_{d | n} I_k(d) \cdot 1 = \sum_{d|n} d^k = \sigma_k(n)$.
- $\displaystyle (\varphi * \textbf{1})(n) = \sum_{d|n}\varphi(d) = n = I(n)$. Otra forma de obtener este resultado es usando el hecho de que tanto $\varphi$ como $\textbf{1}$ son multiplicativas. Hallemos:
$$
\begin{align}
(\varphi * \textbf{1})(p^a) &= \sum_{d | p^a} \varphi(d)\\
&= \sum_{i=0}^{a} \varphi(p^i)\\
&= 1 + \sum_{i=1}^{a} p^i \left( 1 - \dfrac{1}{p} \right)\\
&= 1 + \left( 1 - \dfrac{1}{p} \right) \dfrac{p^{a+1} - p}{p - 1} \\
&= 1 + \dfrac{p-1}{p} \cdot \dfrac{p^{a+1} - p}{p - 1} \\
&= 1 + \dfrac{p^{a+1}-p}{p} \\
&= 1 + p^a - 1 \\
&= p^a \\
&= I(p^a)
\end{align}
$$
Por lo tanto, $(\varphi * \textbf{1})(n) = I(n)$.
- $$
\begin{align}
(\sigma_k * \varphi)(n) &= ((I_k * \textbf{1}) * \varphi)(n)\\
&= (I_k * (\textbf{1} * \varphi))(n)\\
&= (I_k * I)(n)\\
&= \sum_{d|n} I_k(d) I \left( \dfrac{n}{d} \right) \\
&= \sum_{d|n} d^k \cdot \dfrac{n}{d} \\
&= n \sum_{d|n} d^{k-1} \\
&= I(n) \cdot \sigma_{k-1}(n)
\end{align}
$$

# Fórmula de inversión de Möbius
Sean $f, g$ dos funciones aritméticas tales que $g(n) = \displaystyle \sum_{d | n} f(d)$. Entonces, $f(n) = \displaystyle \sum_{d | n} g(d) \mu \left( \dfrac{n}{d} \right)$.

O de forma alternativa, si $g(n) = (f * \textbf{1})(n)$, entonces $f(n) = (g * \mu)(n)$.

En particular, $(\mu * \textbf{1})(n) = \epsilon(n)$.

*Demostración:*
$$
\begin{align}
(\mu * \textbf{1})(p^a) &= \sum_{d | p^a} \mu(d) \\
&= \sum_{i=0}^{a} \mu(p^i) \\
&= 1 + \sum_{i=1}^{a} \mu(p^i) \\
&= 1 - 1 = 0
\end{align}
$$
Pero también sabemos que $(\mu * \textbf{1})(1) = 1$, entonces $(\mu * \textbf{1})(n) = \epsilon(n)$. $\square$

Por ejemplo, si $g(n) = (f * \textbf{1})(n)$, entonces:
$$
\begin{align}
g &= f * \textbf{1} \\
g * \mu &= f * \textbf{1} * \mu \\
g * \mu &= f * \epsilon \\
g * \mu &= f
\end{align}
$$

Ejemplos:
- Sabemos que $\varphi * \textbf{1} = I$, entonces $\varphi = I * \mu$.
- Sabemos que $I_k * \textbf{1} = \sigma_k$, entonces $I_k = \sigma_k * \mu$.

## Ejercicios
### Suma de gcd
Sea $\displaystyle f(n) = \sum_{i=1}^{n} \gcd(i, n)$. Hallar $f(n)$, donde $n \leq 10^{18}$.

Sabemos que $\gcd(i, n) = d$, donde $d | n$. Entonces, $\gcd(i/d, n/d) = 1$. Eso quiere decir que el valor de $d$ aparecerá exactamente $\varphi \left( \dfrac{n}{d} \right)$ veces en la suma.

Por lo tanto, $\displaystyle f(n) = \sum_{d | n} d \cdot \varphi \left( \dfrac{n}{d} \right)$. Pero $f(n) = (I * \varphi)(n)$, y como $I$ y $\varphi$ son multiplicativas, $f$ también lo es.

Entonces,
$$
\begin{align}
f(p^a) &= \sum_{d | p^a} d \cdot \varphi \left( \dfrac{p^a}{d} \right) \\
&= \sum_{i=0}^{a} p^i \cdot \varphi \left( \dfrac{p^a}{p^i} \right) \\
&= \sum_{i=0}^{a} p^i \cdot \varphi(p^{a-i}) \\
&= \sum_{i=0}^{a-1} p^i \cdot \varphi(p^{a-i}) + p^a \\
&= \sum_{i=0}^{a-1} p^i \cdot p^{a-i} \left( 1 - \dfrac{1}{p} \right) + p^a \\
&= \left( 1 - \dfrac{1}{p} \right) \sum_{i=0}^{a-1} p^a + p^a \\
&= \left( 1 - \dfrac{1}{p} \right) a p^a + p^a \\
&= \dfrac{p-1}{p} a p^a + p^a \\
&= p^a \left( a \dfrac{p-1}{p} + 1 \right) \\
&= p^a \left( \dfrac{a(p-1) + p}{p} \right) \\
&= p^{a-1} (a(p-1) + p)
\end{align}
$$

### Suma de lcm
Sea $f(n)=\displaystyle \sum_{i=1}^{n} \text{lcm}(i, n)$. Hallar $f(n)$, donde $n \leq 10^{18}$.

Podemos reescribir a la suma como $f(n)=\displaystyle n\sum_{i=1}^{n} \dfrac{i}{\gcd(i, n)}$.

De forma similar al ejercicio anterior, fijemos un divisor $d$ de $n$ tal que $\gcd(i, n) = d$. Entonces, $\gcd(i/d, n/d) = 1$ y $i=qd$ para algún entero $q$ ($1 \leq q \leq n/d$), por lo tanto, $\gcd(q, n/d)=1$ y la suma se puede reescribir como $f(n) = \displaystyle n \sum_{d | n} \sum_{\gcd(q, n/d)=1} q$.

Sea $h(n) = \displaystyle \sum_{\gcd(q,n)=1} q$ la suma de todos los coprimos a $n$ menores o iguales a $n$. Entonces, $f(n) = \displaystyle n \sum_{d|n} h(n/d) = n\sum_{d|n} h(d)$.

Para hallar a $h(n)$, supongamos que $n \geq 3$. Llamemos a todos los coprimos con $n$ de la siguiente forma: $q_1, q_2, \ldots, q_{\varphi(n)}$. Sabemos que $\gcd(q, n) = \gcd(n-q, n)$ y $q \neq n-q$, por lo tanto, también podemos nombrar a todos los coprimos como $n-q_1, n-q_2, \ldots, n-q_{\varphi(n)}$.

Entonces, $h(n) = q_1 + q_2 + \cdots + q_{\varphi(n)}$, pero también $h(n) = n-q_1 + n-q_2 + \cdots + n-q_{\varphi(n)}$. Sumando ambas ecuaciones, tenemos que $2h(n)=n \varphi(n)$, por lo tanto $h(n) = \dfrac{1}{2} n\varphi(n)$.

El argumento de numerar a los coprimos de esa forma no funciona si $n \leq 2$, pues hay un número impar de ellos. Sin embargo, cuando $n=2$ la fórmula también funciona, pero cuando $n=1$ hay que agregarle $1/2$ para corregirla, entonces podemos decir que $h(n)=\dfrac{1}{2} \left( n \varphi(n) + [n==1] \right)$ para toda $n \in \mathbb{N}$.

Ya teniendo $h(n)$ lista, la sustituímos en $f(n)$: $f(n) = \displaystyle \dfrac{n}{2}\sum_{d|n} (d \varphi(d) + [d==1]) = \dfrac{n}{2} \left( 1 + \sum_{d|n} d \varphi(d) \right)$. Sea $t(n)= \displaystyle \sum_{d|n} d \varphi(d)$, vemos que $t(n)$ es multiplicativa y $f(n)=\dfrac{n}{2} (1 + t(n))$. Finalmente, hallemos $t(n)$ en una potencia de un primo:
$$
\begin{align}
t(p^a) &= \sum_{d | p^a} d \varphi(d) \\
&= \sum_{i=0}^{a} p^i \varphi(p^i) \\
&= 1 + \sum_{i=1}^{a} p^i p^i \left(1 - \dfrac{1}{p} \right) \\
&= 1 + \left(1 - \dfrac{1}{p} \right) \sum_{i=1}^{a} (p^2)^i \\
&= 1 + \dfrac{p-1}{p} \cdot \dfrac{(p^2)^{a+1} - p^2}{p^2-1} \\
&= 1 + \dfrac{p^{2a+1} - p}{p+1} \\
&= \dfrac{p^{2a+1} + 1}{p+1}
\end{align}
$$

# Criba lineal multiplicativa
Queremos evaluar una función multiplicativa $f(n)$ para toda $n$ tal que $1 \leq n \leq N$ ($N \leq 10^7$).

Una forma de hacerlo es factorizar todos los números hasta $N$ con la criba de factor primo más pequeño factorizando un número $x$ con complejidad $O(\log x)$, obteniendo una complejidad total de $O(N \log N)$.

Para lograr una complejidad de $O(N)$, veamos la siguiente modificación de la criba de Eratostenes:

- Sea $lp[d]$ el factor primo más pequeño de $d$.
- Por lo tanto, si $lp[d] = p$, entonces $d = i \cdot p$, donde $p \leq lp[i]$. De esta forma, dicha representación para $d$ es única.

Por lo tanto, la implementación de una criba con complejidad $O(N)$ queda como:

vector<int> sieve(int n){
	vector<int> primes;
	vector<int> lp(n+1);
	for(int i = 2; i <= n; ++i){
		if(lp[i] == 0){
			primes.push_back(i);
			lp[i] = i;
		}
		for(int p : primes){
			int d = i * p;
			if(d > n) break;
			lp[d] = p;
			if(p == lp[i]){
				break;
			}
		}
	}
	return primes;
}

Podemos modificar dicha criba para hallar la función multiplicativa, también con complejidad $O(N)$:

int g(int p, int a){
	//Ejemplo para la phi de euler
	return power(p, a - 1) * (p - 1);
}

vector<int> sieve(int n){
	vector<int> primes;
	vector<int> lp(n+1);  //factor primo mas pequeño de i
	vector<int> f(n+1);   //funcion multiplicativa evaluada en i
	vector<int> cnt(n+1); //exponente del primo mas pequeño de i
	vector<int> pot(n+1); //pow(lp[i], cnt[i])
	f[1] = 1;
	for(int i = 2; i <= n; ++i){
		if(lp[i] == 0){
			primes.push_back(i);
			lp[i] = i;
			f[i] = g(i, 1);
			cnt[i] = 1;
			pot[i] = i;
		}
		for(int p : primes){
			int d = i * p;
			if(d > n) break;
			lp[d] = p;
			if(p == lp[i]){
				// p = lp[i]
				// gcd(p, i) = p
				f[d] = f[i / pot[i]] * g(p, cnt[i]+1);
				cnt[d] = cnt[i] + 1;
				pot[d] = pot[i] * p;
				break;
			}else{
				// p < lp[i]
				// gcd(p, i) = 1
				f[d] = f[i] * f[p];
				cnt[d] = 1;
				pot[d] = p;
			}
		}
	}
	return f;
}