La función de Euler, denotada como φ(n), cuenta el número de enteros positivos menores o iguales a n que son coprimos con n. Dos enteros a y b son coprimos si su máximo común divisor (MCD) es 1.

Fórmula de la Función de Euler

Si la factorización prima de n es n = p₁c₁ ⋅ p₂c₂ ⋅ ... ⋅ pmcm, entonces la función de Euler se calcula como:

φ(n) = n ⋅ ∏i=1m (1 - 1/pi)

Demostración:

Un entero es coprimo con n si y solo si no comparte ningún factor primo con n. Consideramos los números en el rango [1, n]. Hay n/pi múltiplos de cada factor primo pi de n. Por el principio de inclusión-exclusión, el número de enteros en [1, n] que no son múltiplos de ningún factor primo de n es:

n - ∑(n/pi) + ∑(n/(pipj)) - ...

Esto es equivalente a la fórmula:

φ(n) = n ⋅ (1 - 1/p₁) ⋅ (1 - 1/p₂) ⋅ ... ⋅ (1 - 1/pm)

Ejemplo de Código (Cálculo Directo)

#include <iostream>

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

int main() {
    int numero;
    std::cin >> numero;
    std::cout << calcular_euler(numero) << std::endl;
    return 0;
}
</iostream>

Nota: En el contexto de esta explicación, pi representa un factor primo y p representa un número primo.

Propiedades Básicas

Propiedad 1: φ(1) = 1

El único entero positivo menor o igual a 1 es 1, y gcd(1, 1) = 1. Por lo tanto, φ(1) = 1.

Propiedad 2: Para cualquier primo p, φ(p) = p - 1

Todos los enteros desde 1 hasta p-1 son coprimos con p, ya que p solo tiene 1 y p como divisores.

Propiedad 3: Para cualquier primo p y entero k ≥ 1, φ(pk) = pk - pk-1 = pk-1(p - 1)

Demostración: Los números en el rango [1, pk] que no son coprimos con pk son los múltiplos de p. Estos son p, 2p, 3p, ..., pk-1p = pk. Hay pk-1 de tales múltiplos. Por lo tanto, el número de enteros coprimos es pk - pk-1.

Propeidad 4: Si gcd(n, m) = 1, entonces φ(n ⋅ m) = φ(n) ⋅ φ(m). La función de Euler es multiplicativa.

Demostración: Si n y m son coprimos, sus conjuntos de factores primos son disjuntos. Usando la fórmula del producto, se puede demostrar que:

φ(n ⋅ m) = (n ⋅ m) ⋅ ∏p|nm (1 - 1/p) = n ⋅ ∏p|n (1 - 1/p) ⋅ m ⋅ ∏p|m (1 - 1/p) = φ(n) ⋅ φ(m)

Propiedad 5: Para un primo p, si p | n, entonces φ(n ⋅ p) = φ(n) ⋅ p. Si p ∤ n, entonces φ(n ⋅ p) = φ(n) ⋅ φ(p).

**Demostración:**Caso 1: p | n. Sea n = pk ⋅ s, donde gcd(s, p) = 1. Entonces n ⋅ p = pk+1 ⋅ s. Como φ es multiplicativa y φ(pk+1) = pk+1 - pk = p(pk - pk-1) = p ⋅ φ(pk): φ(n ⋅ p) = φ(s) ⋅ φ(pk+1) = φ(s) ⋅ p ⋅ φ(pk) = p ⋅ (φ(s) ⋅ φ(pk)) = p ⋅ φ(n). Caso 2: p ∤ n. Como gcd(n, p) = 1, y φ es multiplicativa: φ(n ⋅ p) = φ(n) ⋅ φ(p) = φ(n) ⋅ (p - 1).

Propiedad 6: Para cualquier n > 2, 2 | φ(n).

**Demostración:**Si n = 2k para k > 1, entonces φ(n) = 2k - 2k-1 = 2k-1, que es par. Si n tiene un factor primo impar p, entonces φ(n) tiene un factor φ(pk) = pk - pk-1 = pk-1(p - 1). Como p - 1 es par, φ(n) es par. Si n = 2, φ(2) = 1, que no es par. Sin embargo, la propiedad es para n > 2.

Propiedad 7: Para cualquier n > 1, la suma de los enteros coprimos con n en el rango [1, n] es n ⋅ φ(n) / 2.

Demostración: Si m es coprimo con n, entonces n - m también es coprimo con n. Estos pares (m, n - m) suman n. Hay φ(n) / 2 de tales pares.

Propiedad 8: ∑d|n φ(d) = n

Demostración: Esta propiedad se puede demostrar utilizendo la multiplicidad de la función φ y considerando el caso de potencias de primos.

Propiedad 9: Si gcd(m, a) = 1, entonces aφ(m) ≡ 1 (mod m). (Pequeño Teorema de Fermat Generalizado)

Demostración: Consideremos el conjunto de enteros coprimos con m en el rango [1, m]: {x₁, x₂, ..., xφ(m)}. Si gcd(a, m) = 1, entonces el conjunto {ax₁, ax₂, ..., axφ(m)} también forma un sistema de residuos coprimos módulo m. Multiplicando todos los elementos de ambos conjuntos y usando la propiedad de congruencia:

∏i=1φ(m) (axi) ≡ ∏i=1φ(m) xi (mod m)

aφ(m) ⋅ ∏i=1φ(m) xi ≡ ∏i=1φ(m) xi (mod m)

Como gcd(∏xi, m) = 1, podemos dividir ambos lados por ∏xi:

aφ(m) ≡ 1 (mod m)

Cálculo de la Función de Euler en un Rango

La función de Euler se puede calcular eficientemente para todos los números en un rango [1, n] utilizando métodos de tamizado.

Tamiz de Eratóstenes Modificado

Podemos adaptar el Tamiz de Eratóstenes para calcular φ(n) para todos los n hasta un límite dado. La idea es que cuando encontramos un primo p, actualizamos φ para todos sus múltiplos.

#include <vector>
#include <iostream>

int main() {
    int n;
    std::cin >> n;
    std::vector<double> phi(n + 1);
    for (int i = 0; i <= n; ++i) {
        phi[i] = i;
    }

    for (int i = 2; i <= n; ++i) {
        if (phi[i] == i) { // i es primo
            for (int j = i; j <= n; j += i) {
                phi[j] = phi[j] * (i - 1) / i;
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        std::cout << static_cast<int>(phi[i]) << std::endl;
    }
    return 0;
}
</int></double></iostream></vector>

Tamiz Lineal

Utilizando la Propiedad 5, podemos construir un tamiz lineal que calcula φ(n) en tiempo O(n).

#include <vector>
#include <iostream>

int main() {
    int n;
    std::cin >> n;
    std::vector<double> phi(n + 1);
    std::vector<int> primes;
    std::vector<bool> is_prime(n + 1, true);

    phi[1] = 1;
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            phi[i] = i - 1;
        }
        for (int p : primes) {
            if (i * p > n) break;
            is_prime[i * p] = false;
            if (i % p == 0) {
                phi[i * p] = phi[i] * p;
                break;
            } else {
                phi[i * p] = phi[i] * phi[p];
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        std::cout << static_cast<int>(phi[i]) << std::endl;
    }
    return 0;
}
</int></bool></int></double></iostream></vector>