φ(n)
Fatores primos
Fração de primos com n
Divisores

          Mostrar

          Mais sobre a função totiente de Euler

          Calculadora da função totiente de Euler

          Dos números de 1 a 12, só 1, 5, 7 e 11 não têm nenhum fator comum com 12, por isso φ(12) = 4. A função totiente de Euler conta estes números primos com n para qualquer n. Introduza um número até 10^18 para obter φ(n) com os seus fatores primos e a fórmula do produto escrita por extenso, ver os números de 1 a n com os primos com n destacados, verificar o teorema de Euler, representar φ(k) para até 100.000 números de uma vez ou encontrar todos os n com um dado φ(n). Introduza um número inteiro n até 10^18 ou escolha um exemplo resolvido. Os mosaicos mostram φ(n), os fatores primos de n, a fração dos números de 1 a n que são primos entre si com n e o número de divisores, e os passos escrevem a fórmula do produto com os seus números. Até n = 500 os números de 1 a n são desenhados: os que são primos com n aparecem preenchidos e os outros com a cor do menor primo que partilham com n. Aponte para um número para ver o seu mdc com n e clique nele para o usar como a no teorema de Euler. Gráfico mostra φ(k) para cada k até um limite; clique num ponto para abrir esse número. Inversa lista todos os n com φ(n) = m; clique num deles para o abrir.

          Como funciona

          1. Introduza um número inteiro n até 10^18 ou escolha um exemplo resolvido como φ(60), um módulo RSA ou o número de Carmichael 561.
          2. Leia φ(n), os fatores primos e a fórmula do produto com os seus números. Até 500, aponte para os números de 1 a n para ver o seu mdc com n e clique num deles para verificar com ele o teorema de Euler.
          3. Mude para Gráfico para ver φ(k) para cada k até 100.000, ou para Inversa para listar todos os n com φ(n) = m.

          Como se calcula φ(n)

          Fatorize n em primos e multiplique n por (1 − 1/p) para cada primo p que o divide. Para 60 = 2² × 3 × 5 obtém-se 60 × 1/2 × 2/3 × 4/5 = 16. Riscar dá a mesma contagem: dos 60 números, 30 são pares; dos 30 ímpares, 10 são múltiplos de 3; dos 20 que restam, 4 são múltiplos de 5, e ficam 16. Para uma potência de um primo a fórmula é φ(p^k) = p^(k−1)(p − 1), e os valores multiplicam-se: φ(60) = 2 × 2 × 4. O difícil é a fatorização. A calculadora usa divisões sucessivas, um teste de primalidade de Miller-Rabin e o método rho de Pollard, pelo que mesmo um produto de 18 algarismos de dois primos de 9 algarismos leva uma fração de segundo.

          Onde a função totiente é usada

          φ(n) conta as frações k/n entre 0 e 1 que já são irredutíveis, os passos que levam um ponteiro por todas as horas de um relógio de n horas (1, 5, 7 e 11 num relógio de 12 horas) e os números que têm inverso módulo n. Euler demonstrou que a^φ(n) ≡ 1 (mod n) para todo o a primo com n, e a cifra RSA assenta nisso: com n = 3233 = 61 × 53, φ(n) = 60 × 52 = 3.120, e o expoente público 17 tem como par privado 2.753, porque 17 × 2.753 = 15 × 3.120 + 1.

          Perguntas frequentes

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

          φ(n) é a quantidade de números inteiros de 1 a n que não têm nenhum fator comum com n além de 1. φ(9) = 6, porque 1, 2, 4, 5, 7 e 8 são primos com 9, enquanto 3, 6 e 9 partilham o fator 3. Por convenção, φ(1) = 1. Euler estudou a função na década de 1760; Gauss deu-lhe o símbolo φ em 1801 e James Joseph Sylvester o nome inglês totient em 1879.

          Quanto vale φ de um número primo?

          p − 1, porque todo número de 1 a p − 1 é primo com um primo p, por isso φ(97) = 96. Para uma potência de um primo, φ(p^k) = p^k − p^(k−1), porque só os múltiplos de p partilham um fator com ela: φ(81) = 81 − 27 = 54.

          O que diz o teorema de Euler?

          Se a e n são primos entre si, então a^φ(n) deixa resto 1 na divisão por n. Para n = 60 e a = 7: φ(60) = 16, e 7^16 ≡ 1 (mod 60). O pequeno teorema de Fermat é o caso de n primo. Muitas vezes já basta um expoente menor: 7^4 = 2.401 = 40 × 60 + 1. O menor expoente que funciona para todo o a primo com n é a função de Carmichael λ(n), que para 60 é 4.

          Dois números podem ter o mesmo totiente?

          Sim, e normalmente são vários: φ(n) = 24 para n = 35, 39, 45, 52, 56, 70, 72, 78, 84 e 90. Alguns números pares nunca são um valor de φ, sendo 14 o menor, e nenhum número ímpar maior do que 1 o é, porque φ(n) é par a partir de n = 3. Robert Carmichael afirmou em 1907 que nenhum valor é atingido exatamente uma vez. Continua por demonstrar, e Kevin Ford mostrou em 1998 que uma exceção teria de ser maior do que 10^(10^10).

          Que tamanho de número posso introduzir?

          Qualquer inteiro até 10^18. A calculadora fatoriza-o com aritmética inteira exata no seu navegador, pelo que φ(10^18) = 4 × 10^17 e φ(999.999.866.000.004.473) = 999.999.864.000.004.608 saem exatos até ao último algarismo. Os números de 1 a n são desenhados até 500, o gráfico vai até 100.000 e a inversa funciona para valores até 10^10.

          Pronto para experimentar?

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

          Ir para o editor