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}$$
As seguintes propriedades da função totiente de Euler são suficientes para calculá-la para qualquer número:
Se $p$ é um número primo, então $\ mdc(p, q) = 1$ para todo $1 \le q < p$. Portanto teremos: $$\phi (p) = p - 1.$$
Se $p$ é um número primo e $k \ge 1$, então existem exatamente $p^k / p$ números entre $1$ e $p^k$ que são divisíveis por $p$. O que nos dá: $$\phi(p^k) = p^k - p^{k-1}.$$
Se $a$ e $b$ são primos entre si, então: $$\phi(a b) = \phi(a) \cdot \phi(b).$$ Essa relação não é trivial de se ver. Segue-se do teorema chinês do resto. O teorema chinês do resto garante que, para cada $0 \le x < a$ e cada $0 \le y < b$, exista um único $0 \le z < a b$ com $z \equiv x \pmod{a}$ e $z \equiv y \pmod{b}$. Não é difícil mostrar que $z$ é coprimo de $a b$ se, e apenas se, $x$ é corpimo de $a$ e $y$ é corpimo de $b$. Portanto, a quantidade de números inteiros coprimos de $a b$ é igual ao produto das quantidades de $a$ e $b$.
No geral, para números não coprimos $a$ e $b$, a equação $$\phi(ab) = \phi(a) \cdot \phi(b) \cdot \dfrac{d}{\phi(d)}$$ com $d = \ mdc(a, b)$ é válida.
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}$$
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;
}
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.
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.$$