A função totiente de Euler explicada

Escreva os números de 1 a 10 e risque cada um que partilhe um fator com 10. Ficam quatro: 1, 3, 7 e 9. Essa contagem, φ(10) = 4, é a função totiente de Euler, uma das funções mais usadas da teoria dos números, das frações e dos relógios até à cifra que protege os pagamentos online.

Os números de 1 a 30 numa grelha com preenchidos os oito que são primos com 30, a fórmula φ(30) = 30 × 1/2 × 2/3 × 4/5 = 8 e um gráfico de φ(k) com os primos sobre uma reta
Os números de 1 a 30 numa grelha com preenchidos os oito que são primos com 30, a fórmula φ(30) = 30 × 1/2 × 2/3 × 4/5 = 8 e um gráfico de φ(k) com os primos sobre uma reta

Contar números primos entre si

Dois números são primos entre si quando o seu máximo divisor comum é 1. φ(n) conta os k de 1 a n com mdc(k, n) = 1: φ(9) = 6, φ(10) = 4, φ(12) = 4 e φ(1) = 1. A mesma contagem aparece em muitos sítios. É o número de frações k/n entre 0 e 1 que já são irredutíveis, o número de passos que levam um ponteiro por todas as horas de um relógio de n horas e o número de k que têm inverso módulo n, de forma que k × x ≡ 1 (mod n) tem solução.

A fórmula do produto

Se os primos que dividem n são p₁, p₂ …, então φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × …. A razão é um crivo. Metade de todos os números são pares, por isso retirar os múltiplos de 2 deixa a fração 1 − 1/2; dos números que restam, um em cada três é múltiplo de 3, e assim por diante. Pelo teorema chinês dos restos, as condições para primos diferentes são independentes, por isso as frações simplesmente multiplicam-se. Para 100 = 2² × 5² obtém-se 100 × 1/2 × 4/5 = 40. Duas propriedades dão o mesmo resultado de outra forma: φ(p^k) = p^(k−1)(p − 1), e φ(mn) = φ(m) φ(n) quando m e n são primos entre si, pelo que φ(100) = φ(4) × φ(25) = 2 × 20 = 40.

O teorema de Euler

Fermat reparou em 1640 que a^(p−1) ≡ 1 (mod p) para um primo p e qualquer a que p não divida. Euler demonstrou a versão geral, publicada em 1763: a^φ(n) ≡ 1 (mod n) sempre que mdc(a, n) = 1. A demonstração é curta. Multiplique por a os φ(n) números primos com n; os produtos voltam a ser primos com n e são todos diferentes módulo n, logo são os mesmos números noutra ordem, e comparando os dois produtos resta a^φ(n) ≡ 1. O menor expoente que funciona para um dado a é a sua ordem, que divide sempre φ(n); o menor que funciona para todos os a ao mesmo tempo é a função de Carmichael λ(n). Para 561 = 3 × 11 × 17, λ(561) = 80 divide 560, pelo que a^560 ≡ 1 (mod 561) para todo o a primo com 561, embora 561 não seja primo. É o menor número de Carmichael e a razão pela qual o teste de Fermat sozinho não consegue provar que um número é primo.

Leonhard Euler, num retrato de Jakob Emanuel Handmann. Em 1763 publicou a forma geral da observação de Fermat: a^φ(n) ≡ 1 (mod n) quando a e n são coprimos.
Leonhard Euler, num retrato de Jakob Emanuel Handmann. Em 1763 publicou a forma geral da observação de Fermat: a^φ(n) ≡ 1 (mod n) quando a e n são coprimos.

A soma sobre divisores de Gauss e a média

Some φ(d) sobre os divisores d de n e obtém sempre n de volta: para 12, φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12. Gauss demonstrou-o nas suas Disquisitiones Arithmeticae de 1801; vê-se simplificando as frações 1/12, 2/12 … 12/12 e ordenando-as pelo denominador. Em média, φ(k) é cerca de 0,61 k: a média de φ(k)/k tende para 6/π² ≈ 0,6079, que é também a probabilidade de dois inteiros ao acaso serem primos entre si, e φ(1) + … + φ(N) fica próxima de 3N²/π². Para N = 1.000 a soma é 304.192, contra 3N²/π² ≈ 303.964.

Carl Friedrich Gauss, num retrato de Christian Albrecht Jensen de 1840. Introduziu a notação de congruência a ≡ b (mod n) nas Disquisitiones Arithmeticae de 1801.
Carl Friedrich Gauss, num retrato de Christian Albrecht Jensen de 1840. Introduziu a notação de congruência a ≡ b (mod n) nas Disquisitiones Arithmeticae de 1801.

Valores que nunca ocorrem

φ(n) é par para todo o n a partir de 3, porque os números primos com n vêm aos pares, k e n − k. Também nem todo o número par é um valor: 14, 26, 34, 38 e 50 são os primeiros que nunca ocorrem, enquanto 24 é o valor de dez números diferentes, de 35 a 90. Encontrá-los é uma pesquisa finita, porque para cada primo p que divide n, p − 1 tem de dividir φ(n). Em 1907 Robert Carmichael afirmou que nenhum valor é atingido exatamente uma vez. A sua demonstração estava errada, a afirmação continua em aberto e qualquer exceção teria de ser maior do que 10^(10^10). D. H. Lehmer perguntou em 1932 se φ(n) pode dividir n − 1 para um n composto; não se conhece nenhum exemplo.

A função totiente no RSA

O RSA escolhe dois primos grandes p e q e publica n = pq e um expoente e. Como φ(n) = (p − 1)(q − 1), quem conseguir fatorizar n pode calcular φ(n) e, a partir dele, o expoente privado d com e × d ≡ 1 (mod φ(n)); o teorema de Euler garante então que (m^e)^d ≡ m (mod n). No exemplo clássico n = 3233 = 61 × 53, φ(n) = 3.120, e = 17 e d = 2.753. Muitas implementações usam antes λ(n) = mmc(p − 1, q − 1), aqui 780, o que dá o d menor 413. Calcular φ(n) para um módulo RSA de 600 algarismos é tão difícil como fatorizá-lo: a partir de n e φ(n), os dois primos obtêm-se com uma única raiz quadrada.

Ron Rivest, Adi Shamir e Len Adleman (da esquerda para a direita)
Ron Rivest, Adi Shamir e Len Adleman (da esquerda para a direita)

Explore

Abra a calculadora e introduza qualquer n até 10^18 para ver φ(n) com os fatores primos e a fórmula. Até 500 os números de 1 a n são desenhados, os primos com n preenchidos e os outros coloridos segundo o menor primo que partilham com n, de modo que a fórmula do produto se torna um crivo que se pode contar. Escolha um número a para verificar o teorema de Euler, mude para Gráfico para ver φ(k) até 100.000 com os primos sobre a reta φ(p) = p − 1, ou para Inversa para encontrar todos os n com φ(n) = m.

Perguntas frequentes

Porque é que φ(1) = 1?

Porque mdc(1, 1) = 1: o único número de 1 a 1 é primo com 1. A convenção também mantém as fórmulas válidas, por exemplo a soma de Gauss sobre os divisores de n, que para n = 1 é simplesmente φ(1) = 1.

φ é o mesmo que a função de contagem de primos?

Não. π(n) conta os primos até n, φ(n) os números até n que são primos com n. φ(10) = 4 conta 1, 3, 7 e 9, enquanto π(10) = 4 conta 2, 3, 5 e 7. Aqui coincidem por acaso: φ(12) = 4, mas π(12) = 5.

Com que rapidez se calcula φ(n)?

Tão depressa quanto se consegue fatorizar n. Com os fatores primos conhecidos bastam algumas multiplicações; sem eles não se conhece nenhum método rápido, e é nisso que o RSA assenta. Para números até 10^18 a fatorização leva milissegundos num navegador; para números com centenas de algarismos pode levar anos.

Que números têm o menor φ(n) em relação a n?

Os números com muitos fatores primos pequenos. φ(n)/n = (1 − 1/p₁)(1 − 1/p₂)… só depende de quais primos dividem n, não das suas potências: para qualquer potência de 2 é exatamente 1/2, e para 30 = 2 × 3 × 5 é 8/30, cerca de 27 %. O produto dos 15 primeiros primos, 614.889.782.588.491.410, tem φ(n)/n ≈ 14 %, o valor mais baixo de todos os números até 10^18.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Abrir a calculadora