Función φ de Euler

La función φ de Euler, también conocida como función phi $\phi (n)$ , cuenta la cantidad de enteros entre 1 y $n$ inclusive que son coprimos con $n$ . Dos números son coprimos si su máximo común divisor es igual a $1$ (se considera que $1$ es coprimo con cualquier número).

Estos son los valores de $\phi(n)$ para los primeros enteros positivos:

$\begin{array}{cccccccccccccccccccccc} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 \\ ϕ (n) & 1 & 1 & 2 & 2 & 4 & 2 & 6 & 4 & 6 & 4 & 10 & 4 & 12 & 6 & 8 & 8 & 16 & 6 & 18 & 8 & 12 \end{array}$

Propiedades

Las siguientes propiedades de la función φ de Euler bastan para calcularla para cualquier número:

Si $p$ es un número primo, entonces $\gcd(p, q) = 1$ para todo $1 \le q < p$ . Por lo tanto tenemos:

$\phi (p) = p - 1.$

Si $p$ es un número primo y $k \ge 1$ , entonces hay exactamente $p^k / p$ números entre $1$ y $p^k$ que son divisibles por $p$ . Lo que nos da:

$\phi(p^k) = p^k - p^{k-1}.$

Si $a$ y $b$ son coprimos, entonces:

$\phi(a b) = \phi(a) \cdot \phi(b).$

Esta relación no es trivial de ver. Se sigue del Teorema Chino del Resto. El Teorema Chino del Resto garantiza que, para cada $0 \le x < a$ y cada $0 \le y < b$ , existe un único $0 \le z < a b$ con $z \equiv x \pmod{a}$ y $z \equiv y \pmod{b}$ . No es difícil mostrar que $z$ es coprimo con $a b$ si y solo si $x$ es coprimo con $a$ e $y$ es coprimo con $b$ . Por lo tanto, la cantidad de enteros coprimos con $a b$ es igual al producto de las cantidades correspondientes a $a$ y a $b$ .
En general, cuando $a$ y $b$ no son coprimos, la ecuación

$\phi(ab) = \phi(a) \cdot \phi(b) \cdot \dfrac{d}{\phi(d)}$

con $d = \gcd(a, b)$ se cumple.

Así, usando las primeras tres propiedades, podemos calcular $\phi(n)$ a través de la factorización de $n$ (descomposición de $n$ en un producto de sus factores primos). Si $n = {p_1}^{a_1} \cdot {p_2}^{a_2} \cdots {p_k}^{a_k}$ , donde $p_i$ son factores primos de $n$ ,

$\begin{aligned} ϕ (n) & = ϕ ({p_{1}}^{a_{1}}) \cdot ϕ ({p_{2}}^{a_{2}}) \dots ϕ ({p_{k}}^{a_{k}}) \\ = ({p_{1}}^{a_{1}} - {p_{1}}^{a_{1} - 1}) \cdot ({p_{2}}^{a_{2}} - {p_{2}}^{a_{2} - 1}) \dots ({p_{k}}^{a_{k}} - {p_{k}}^{a_{k} - 1}) \\ = p_{1}^{a_{1}} \cdot (1 - \frac{1}{p_{1}}) \cdot p_{2}^{a_{2}} \cdot (1 - \frac{1}{p_{2}}) \dots p_{k}^{a_{k}} \cdot (1 - \frac{1}{p_{k}}) \\ = n \cdot (1 - \frac{1}{p_{1}}) \cdot (1 - \frac{1}{p_{2}}) \dots (1 - \frac{1}{p_{k}}) \end{aligned}$

Implementación

Esta es una implementación que usa factorización en $O(\sqrt{n})$ :


int phi(int n) {
    int result = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    }
    if (n > 1)
        result -= result / n;
    return result;
}

Función φ de Euler de $1$ a $n$ en $O(n \log\log{n})$ { #etf_1_to_n data-toc-label=“Función φ de Euler de 1 a n en <script type=“math/tex”>O(n log log n)” }

Si necesitamos $\phi$ de todos los números entre $1$ y $n$ , entonces factorizar los $n$ números no es eficiente. Podemos usar la misma idea que la Criba de Eratóstenes. Sigue basándose en la propiedad mostrada más arriba, pero en lugar de actualizar el resultado temporal para cada factor primo de cada número, encontramos todos los números primos y, para cada uno, actualizamos los resultados temporales de todos los números que son divisibles por ese número primo.

Como este enfoque es básicamente idéntico a la Criba de Eratóstenes, la complejidad también será la misma: $O(n \log \log n)$


void phi_1_to_n(int n) {
    vector<int> phi(n + 1);
    for (int i = 0; i <= n; i++)
        phi[i] = i;
    
    for (int i = 2; i <= n; i++) {
        if (phi[i] == i) {
            for (int j = i; j <= n; j += i)
                phi[j] -= phi[j] / i;
        }
    }
}

Calcular φ de $L$ a $R$ usando la criba segmentada { data-toc-label=“Calcular φ de L a R usando la criba segmentada” }

Si necesitamos $\phi$ de todos los números entre $L$ y $R$ , podemos usar el enfoque de la criba segmentada.

El algoritmo primero precalcula todos los primos hasta $\sqrt{R}$ usando una criba lineal en tiempo y espacio $O(\sqrt{R})$ . Para cada número del rango $[L, R]$ , aplica después la fórmula de $\phi$ basada en la factorización iterando sobre estos primos. Mantenemos un arreglo de restos para rastrear la parte no factorizada de cada número. Si un resto sigue siendo mayor que 1 después de procesar todos los primos chicos, indica un factor primo grande mayor que $\sqrt{R}$ , que se trata en una pasada final. La complejidad total del cálculo sobre el rango es $O((R - L + 1) \log \log R) + \sqrt{R}$ .


const long long MAX_RANGE = 1e6 + 6;
vector<long long> primes;
long long phi[MAX_RANGE], rem[MAX_RANGE];
 
vector<int> linear_sieve(int n) { 
    vector<bool> composite(n + 1, 0);
    vector<int> prime;
 
    // 0 y 1 no son compuestos (ni primos)
    composite[0] = composite[1] = 1;
 
    for(int i = 2; i <= n; i++) {
        if(!composite[i]) prime.push_back(i);
        for(int j = 0; j < prime.size() && i * prime[j] <= n; j++) {
            composite[i * prime[j]] = true;
            if(i % prime[j] == 0) break;
        }
    }
    return prime;
}
 
// Para obtener el valor de phi(x) con L <= x <= R, usar phi[x - L].
void segmented_phi(long long L, long long R) { 
    for(long long i = L; i <= R; i++) {
        rem[i - L] = i;
        phi[i - L] = i;
    }
 
    for(long long i : primes) {
        for(long long j = max(i * i, (L + i - 1) / i * i); j <= R; j += i) {
            phi[j - L] -= phi[j - L] / i;
            while(rem[j - L] % i == 0) rem[j - L] /= i;
        }
    }
 
    for(long long i = 0; i < R - L + 1; i++) {
        if(rem[i] > 1) phi[i] -= phi[i] / rem[i];
    }
}

Propiedad de la suma de divisores { #divsum}

Esta propiedad interesante la estableció Gauss:

$\sum_{d|n} \phi{(d)} = n$

Aquí la suma recorre todos los divisores positivos $d$ de $n$ .

Por ejemplo, los divisores de 10 son 1, 2, 5 y 10. De ahí $\phi{(1)} + \phi{(2)} + \phi{(5)} + \phi{(10)} = 1 + 1 + 4 + 4 = 10$ .

Calcular φ de 1 a $n$ usando la propiedad de la suma de divisores { data-toc-label=“Calcular φ de 1 a n usando la propiedad de la suma de divisores” }

La propiedad de la suma de divisores también nos permite calcular $\phi$ de todos los números entre 1 y $n$ . Esta implementación es un poco más simple que la implementación anterior basada en la Criba de Eratóstenes; sin embargo, también tiene una complejidad un poco peor: $O(n \log n)$


void phi_1_to_n(int n) {
    vector<int> phi(n + 1);
    phi[0] = 0;
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
        phi[i] = i - 1;
    
    for (int i = 2; i <= n; i++)
        for (int j = 2 * i; j <= n; j += i)
              phi[j] -= phi[i];
}

Aplicación en el teorema de Euler { #application }

La propiedad más famosa e importante de la función φ de Euler se expresa en el teorema de Euler:

$a^{\phi(m)} \equiv 1 \pmod m \quad \text{if } a \text{ and } m \text{ are relatively prime.}$

En el caso particular en que $m$ es primo, el teorema de Euler se convierte en el pequeño teorema de Fermat:

$a^{m - 1} \equiv 1 \pmod m$

El teorema de Euler y la función φ de Euler aparecen con bastante frecuencia en aplicaciones prácticas; por ejemplo, ambos se usan para calcular el inverso multiplicativo modular.

Como consecuencia inmediata también obtenemos la equivalencia:

$a^n \equiv a^{n \bmod \phi(m)} \pmod m$

Esto permite calcular $x^n \bmod m$ para $n$ muy grandes, especialmente si $n$ es el resultado de otro cálculo, ya que permite calcular $n$ bajo un módulo.

Teoría de grupos

$\phi(n)$ es el orden del grupo multiplicativo módulo n $(\mathbb Z / n\mathbb Z)^\times$ , es decir, el grupo de unidades (elementos con inversos multiplicativos). Los elementos con inversos multiplicativos son precisamente los coprimos con $n$ .

El orden multiplicativo de un elemento $a$ módulo $n$ , denotado $\operatorname{ord}_n(a)$ , es el menor $k>0$ tal que $a^k \equiv 1 \pmod n$ . $\operatorname{ord}_n(a)$ es el tamaño del subgrupo generado por $a$ , así que, por el teorema de Lagrange, el orden multiplicativo de cualquier $a$ debe dividir a $\phi(n)$ . Si el orden multiplicativo de $a$ es $\phi(n)$ , el mayor posible, entonces $a$ es una raíz primitiva y el grupo es cíclico por definición.

Generalización

Hay una versión menos conocida de la última equivalencia, que permite calcular $x^n \bmod m$ de forma eficiente cuando $x$ y $m$ no son coprimos. Para $x, m$ arbitrarios y $n \geq \log_2 m$ :

$x^{n}\equiv x^{\phi(m)+[n \bmod \phi(m)]} \mod m$

Demostración:

Sean $p_1, \dots, p_t$ los divisores primos comunes de $x$ y $m$ , y $k_i$ sus exponentes en $m$ . Con ellos definimos $a = p_1^{k_1} \dots p_t^{k_t}$ , lo que hace que $\frac{m}{a}$ sea coprimo con $x$ . Y sea $k$ el menor número tal que $a$ divide a $x^k$ . Asumiendo $n \ge k$ , podemos escribir:

$\begin{aligned} x^{n} m o d m & = \frac{x^{k}}{a} a x^{n - k} m o d m \\ = \frac{x^{k}}{a} (a x^{n - k} m o d m) m o d m \\ = \frac{x^{k}}{a} (a x^{n - k} m o d a \frac{m}{a}) m o d m \\ = \frac{x^{k}}{a} a (x^{n - k} m o d \frac{m}{a}) m o d m \\ = x^{k} (x^{n - k} m o d \frac{m}{a}) m o d m \end{aligned}$

La equivalencia entre la tercera y la cuarta línea se sigue del hecho de que $ab \bmod ac = a(b \bmod c)$ . En efecto, si $b = cd + r$ con $r < c$ , entonces $ab = acd + ar$ con $ar < ac$ .

Como $x$ y $\frac{m}{a}$ son coprimos, podemos aplicar el teorema de Euler y obtener la fórmula eficiente (ya que $k$ es muy chico; de hecho $k \le \log_2 m$ ):

$x^n \bmod m = x^k\left(x^{n-k \bmod \phi(\frac{m}{a})} \bmod \frac{m}{a}\right)\bmod m.$

Esta fórmula es difícil de aplicar, pero podemos usarla para analizar el comportamiento de $x^n \bmod m$ . Podemos ver que la sucesión de potencias $(x^1 \bmod m, x^2 \bmod m, x^3 \bmod m, \dots)$ entra en un ciclo de longitud $\phi\left(\frac{m}{a}\right)$ después de los primeros $k$ (o menos) elementos. $\phi\left(\frac{m}{a}\right)$ divide a $\phi(m)$ (porque $a$ y $\frac{m}{a}$ son coprimos tenemos $\phi(a) \cdot \phi\left(\frac{m}{a}\right) = \phi(m)$ ), por lo tanto también podemos decir que el período tiene longitud $\phi(m)$ . Y como $\phi(m) \ge \log_2 m \ge k$ , podemos concluir la fórmula deseada, mucho más simple:

$x^n \equiv x^{\phi(m)} x^{(n - \phi(m)) \bmod \phi(m)} \bmod m \equiv x^{\phi(m)+[n \bmod \phi(m)]} \mod m.$