Última atualização: 2026-07-13

Definição

A função totiente de Euler $\varphi(n)$ conta quantos inteiros de $1$ a $n$ são coprimos com $n$ — isto é, quantos não têm nenhum fator em comum com $n$ além de $1$. Dois inteiros são coprimos quando seu máximo divisor comum é $1$.

Por exemplo, $\varphi(9) = 6$: entre $1, 2, \dots, 9$, os valores $1, 2, 4, 5, 7, 8$ são coprimos com $9$, enquanto $3, 6, 9$ não são.

A função recebe o nome de Leonhard Euler, que a introduziu em 1763. Também é escrita $\phi(n)$ e chamada de função phi.

A fórmula do produto

Não é preciso testar todos os inteiros até $n$. Uma vez que $n$ é decomposto em seus fatores primos distintos, o totiente sai de imediato:

$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$

O produto percorre os primos distintos que dividem $n$ — os expoentes não aparecem. Cada primo $p$ remove a fração $1/p$ dos números (os divisíveis por $p$), e como os primos agem de forma independente, as frações se multiplicam.

Exemplo resolvido — n = 36. A fatoração é $36 = 2^2 \cdot 3^2$, então os primos distintos são $2$ e $3$:

$\varphi(36) = 36\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) = 36 \cdot \frac{1}{2} \cdot \frac{2}{3} = 12$

Os doze inteiros coprimos com $36$ são $1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35$.

Primos e potências de primos

Dois casos básicos tornam a fórmula fácil de entender:

• Primo $p$: todo inteiro de $1$ a $p - 1$ é coprimo com $p$, de modo que $\varphi(p) = p - 1$. Por exemplo $\varphi(7) = 6$.
• Potência de primo $p^k$: os únicos inteiros não coprimos com $p^k$ são os múltiplos de $p$, que são $p^{k-1}$. Portanto

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

Assim $\varphi(8) = \varphi(2^3) = 2^2(2 - 1) = 4$ e $\varphi(27) = \varphi(3^3) = 3^2(3 - 1) = 18$.

Multiplicatividade

O totiente é multiplicativo: sempre que $m$ e $n$ são coprimos,

$\varphi(mn) = \varphi(m)\,\varphi(n)$

É por isso que a fórmula do produto funciona: escreve-se $n$ como produto de potências de primos, aplica-se $\varphi(p^k) = p^{k-1}(p-1)$ a cada uma e multiplica-se. Por exemplo, $36 = 4 \cdot 9$ com $\gcd(4, 9) = 1$, então $\varphi(36) = \varphi(4)\,\varphi(9) = 2 \cdot 6 = 12$.

Atenção à condição de coprimalidade: $\varphi(mn) = \varphi(m)\varphi(n)$ pode falhar quando $m$ e $n$ compartilham um fator. Por exemplo $\varphi(2 \cdot 2) = \varphi(4) = 2$, e não $\varphi(2)\varphi(2) = 1$.

O teorema de Euler

O totiente governa a exponenciação modular. O teorema de Euler afirma que, se $\gcd(a, n) = 1$, então

$a^{\varphi(n)} \equiv 1 \pmod{n}$

Isso generaliza o pequeno teorema de Fermat ($a^{p-1} \equiv 1 \pmod p$ para um primo $p$), que é apenas o caso particular $n = p$, em que $\varphi(p) = p - 1$.

Exemplo. Tome $a = 3$, $n = 10$. Aqui $\varphi(10) = 4$, então $3^4 = 81 \equiv 1 \pmod{10}$ — e de fato $81$ termina em $1$. O teorema permite reduzir expoentes enormes módulo $\varphi(n)$ antes de calcular.

Aplicação no RSA

A criptografia de chave pública RSA é construída diretamente sobre o totiente. Um módulo é formado a partir de dois primos grandes, $n = p \cdot q$, resultando em

$\varphi(n) = (p - 1)(q - 1)$

O expoente público $e$ e o privado $d$ são escolhidos de modo que $e \cdot d \equiv 1 \pmod{\varphi(n)}$. O teorema de Euler garante então que descriptografar inverte criptografar: $(m^e)^d \equiv m \pmod n$.

A segurança repousa sobre uma lacuna: qualquer um pode publicar $n$, mas calcular $\varphi(n) = (p-1)(q-1)$ exige conhecer $p$ e $q$. Recuperá-los só a partir de $n$ é fatorar um semiprimo grande — algo tido como computacionalmente inviável para primos suficientemente grandes. Na verdade, conhecer $\varphi(n)$ equivale a fatorar $n$.

Exemplos resolvidos

$n$	Fatoração	Forma de produto	$\varphi(n)$
$10$	$2 \cdot 5$	$10\,(1 - \tfrac12)(1 - \tfrac15)$	$4$
$12$	$2^2 \cdot 3$	$12\,(1 - \tfrac12)(1 - \tfrac13)$	$4$
$36$	$2^2 \cdot 3^2$	$36\,(1 - \tfrac12)(1 - \tfrac13)$	$12$
$100$	$2^2 \cdot 5^2$	$100\,(1 - \tfrac12)(1 - \tfrac15)$	$40$
$101$	$101$ (primo)	$101\,(1 - \tfrac{1}{101})$	$100$

Casos especiais

• $n = 1$: por convenção $\varphi(1) = 1$. O único inteiro do intervalo, $1$, é coprimo consigo mesmo.
• $n$ primo: $\varphi(n) = n - 1$, o máximo possível para esse tamanho — os primos têm a maior quantidade de restos coprimos.
• $n$ par: o fator $(1 - \tfrac12)$ remove ao menos metade dos inteiros, então $\varphi(n) \le n/2$.
• Soma sobre divisores: os totientes de todos os divisores de $n$ somam $n$: $\sum_{d \mid n} \varphi(d) = n$. Para $n = 12$: $\varphi(1) + \varphi(2) + \varphi(3) + \varphi(4) + \varphi(6) + \varphi(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12$.

Referência rápida

Conceito	Fórmula
Definição	$\varphi(n) = \#\{\, k : 1 \le k \le n,\ \gcd(k, n) = 1 \,\}$
Fórmula do produto	$\varphi(n) = n \prod_{p \mid n} (1 - 1/p)$
Primo	$\varphi(p) = p - 1$
Potência de primo	$\varphi(p^k) = p^{k-1}(p - 1)$
Multiplicativa	$\varphi(mn) = \varphi(m)\varphi(n)$ se $\gcd(m, n) = 1$
Teorema de Euler	$a^{\varphi(n)} \equiv 1 \pmod n$ se $\gcd(a, n) = 1$
Soma de divisores	$\sum_{d \mid n} \varphi(d) = n$

Perguntas frequentes (FAQ)

O que é a função totiente de Euler?

A função totiente de Euler φ(n) conta os inteiros positivos até n que são coprimos com n — ou seja, que não têm nenhum fator em comum com n além de 1. Por exemplo, φ(9) = 6, pois 1, 2, 4, 5, 7 e 8 são coprimos com 9, enquanto 3, 6 e 9 não são. Por convenção, φ(1) = 1.

Como calcular φ(n)?

Fatore n em seus primos distintos p₁, p₂, …, pₖ e aplique φ(n) = n · ∏(1 − 1/p) sobre esses primos. Para n = 36 = 2² · 3², φ(36) = 36 · (1 − 1/2) · (1 − 1/3) = 36 · 1/2 · 2/3 = 12. Só contam os primos distintos, não os seus expoentes.

Qual é o totiente de um número primo?

Para um primo p, todo inteiro de 1 a p − 1 é coprimo com p, então φ(p) = p − 1. Para uma potência de primo pᵏ, a fórmula dá φ(pᵏ) = pᵏ − pᵏ⁻¹ = pᵏ⁻¹(p − 1). Por exemplo, φ(7) = 6 e φ(8) = φ(2³) = 8 − 4 = 4.

Por que o totiente importa no RSA e no teorema de Euler?

O teorema de Euler afirma que, se mdc(a, n) = 1, então a^φ(n) ≡ 1 (mod n) — uma generalização do pequeno teorema de Fermat. O RSA se apoia nisso: para um módulo n = p·q de dois primos, φ(n) = (p − 1)(q − 1), e os expoentes público e privado são escolhidos de modo que e·d ≡ 1 (mod φ(n)). Conhecer φ(n) equivale a fatorar n, e é isso que mantém o RSA seguro.