Função totiente de Euler

A função totiente de Euler, também conhecida como função phi $\phi (n)$, conta o número de inteiros entre 1 e $n$, no qual são coprimos de $n$. Dois números são coprimos se o maior divisor comum entre eles for $1$ ($1$ é considerado ser coprimo para qualquer número).

Aqui estão valores de $\phi(n)$ para os primeiros números inteiros positivos: $$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 \\ \hline \phi(n) & 1 & 1 & 2 & 2 & 4 & 2 & 6 & 4 & 6 & 4 & 10 & 4 & 12 & 6 & 8 & 8 & 16 & 6 & 18 & 8 & 12 \\ \hline \end{array}$$

Propriedades

As seguintes propriedades da função totiente de Euler são suficientes para calculá-la para qualquer número:

Assim, usando as três primeiras propriedades, podemos calcular $\phi(n)$ por meio da fatoração de $n$ (decomposição de $n$ em um produto de seus fatores primos). Se $n = {p_1}^{a_1} \cdot {p_2}^{a_2} \cdots {p_k}^{a_k}$, onde $p_i$ são fatores primos de $n$,

$$\begin{align} \phi (n) &= \phi ({p_1}^{a_1}) \cdot \phi ({p_2}^{a_2}) \cdots \phi ({p_k}^{a_k}) \\ &= \left({p_1}^{a_1} - {p_1}^{a_1 - 1}\right) \cdot \left({p_2}^{a_2} - {p_2}^{a_2 - 1}\right) \cdots \left({p_k}^{a_k} - {p_k}^{a_k - 1}\right) \\ &= p_1^{a_1} \cdot \left(1 - \frac{1}{p_1}\right) \cdot p_2^{a_2} \cdot \left(1 - \frac{1}{p_2}\right) \cdots p_k^{a_k} \cdot \left(1 - \frac{1}{p_k}\right) \\ &= n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right) \end{align}$$

Implementação

Aqui está uma implementação usando fatoração em $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;
}

Aplicação no teorema de Euler

A propriedade mais famosa e importante da função totiente de Euler é expressa no teorema de Euler: $$a^{\phi(m)} \equiv 1 \pmod m$$ se $a$ e $m$ forem primos entre si.

No caso específico em que $m$ for primo, o teorema de Euler se transforma no pequeno teorema de Fermat: $$a^{m - 1} \equiv 1 \pmod m$$

O teorema de Euler e a função totiente de Euler ocorrem com bastante frequência em aplicações práticas, por exemplo, ambos são usados ​​para calcular a multiplicação modular inversa.

Como conseqüência imediata, também obtemos a equivalência: $$a^n \equiv a^{n \bmod \phi(m)} \pmod m$$ Isso permite calcular $x^n \bmod m$ para grandes valores de $n$, especificamente se $n$ é o resultado de outro cálculo, pois permite calcular $n$ sob um módulo.

Generalização

Existe uma versão menos conhecida da última equivalência, que permite calcular eficientemente $x^n \bmod m$ para números não coprimos $x$ e $m$. Para arbitrários $x, m$ e $n \geq \log_2 m$: $$x^{n}\equiv x^{\phi(m)+[n \bmod \phi(m)]} \mod m$$

Prova:

Seja $p_1, \dots, p_t$ divisores primos comuns de $x$ e $m$, e $k_i$ seus expoentes em $m$. Com esses, definimos $a = p_1^{k_1} \dots p_t^{k_t}$, o que torna $\frac{m}{a}$ coprimo de $x$. E seja $k$ o menor número, de modo que $a$ divida $x^k$. Assumindo $n \ge k$, podemos escrever:

$$\begin{align}x^n \bmod m &= \frac{x^k}{a}ax^{n-k}\bmod m \\ &= \frac{x^k}{a}\left(ax^{n-k}\bmod m\right) \bmod m \\ &= \frac{x^k}{a}\left(ax^{n-k}\bmod a \frac{m}{a}\right) \bmod m \\ &=\frac{x^k}{a} a \left(x^{n-k} \bmod \frac{m}{a}\right)\bmod m \\ &= x^k\left(x^{n-k} \bmod \frac{m}{a}\right)\bmod m \end{align}$$

A equivalência entre a terceira e a quarta linha decorre do fato de que $ab \bmod ac = a(b \bmod c)$. De fato, se $b = cd + r$ com $r < c$, então $ab = acd + ar$ com $ar < ac$.

Como $x$ e $\frac{m}{a}$ são coprimos, podemos aplicar o teorema de Euler e obter a fórmula eficiente (já que $k$ é muito pequeno; de fato $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.$$

Essa fórmula é difícil de aplicar, mas podemos usá-la para analisar o comportamento de $x^n \bmod m$. Podemos ver que a sequência de potências $(x^1 \bmod m, x^2 \bmod m, x^3 \bmod m, \dots)$ entra em um ciclo de tamanho $\phi\left(\frac{m}{a}\right)$ após os primeiros $k$ (ou menores) elementos. $\phi\left(\frac{m}{a}\right)$ divide $\phi(m)$ (pois $a$ e $\frac{m}{a}$ são coprimos, temos $\phi(a) \cdot \phi\left(\frac{m}{a}\right) = \phi(m)$), portanto também podemos dizer que o período tem duração $\phi(m)$. E como $\phi(m) \ge \log_2 m \ge k$, podemos concluir com uma fórmula mais desejada e simples: $$ 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.$$

Problemas