Um primo é o número coprimo com quase tudo o que está abaixo
Publicado a 27/10/2026 · 3 min de leitura · Calculadoras do dia a dia
Daniel Okonkwo — Programador front-end e redator de Tecnologia na OneKitly
Desempenho web · Formatos de ficheiro
Verificado a partir de 2 fontes
A função totiente de Euler conta quantos números abaixo de n não partilham fator com ele. Para um primo a resposta é tudo: φ(97) = 96, porque 97 não divide nada abaixo. Para um número com fatores pequenos repetidos a resposta desaba — φ(36) = 12 e φ(100) = 40, já que 36 é 2² × 3² e 100 é 2² × 5², e todo o par e todo o múltiplo do outro primo fica desqualificado. A fórmula multiplica n por um menos o inverso de cada fator primo distinto, pelo que os fatores repetidos nada custam de extra e os novos custam muito. É essa toda a razão de as construções criptográficas preferirem os primos: maximizam o número de parceiros utilizáveis.
φ(97) = 96, o maior valor que um número abaixo de cem pode atingir. φ(36) é 12 e φ(100) é 40 — quantos mais fatores primos distintos um número tem, menos companheiros guarda.
A multiplicidade é grátis, a variedade custa caro
Trinta e seis e cem são ambos quadrados de números livres de quadrados e perdem da mesma maneira, mas cem guarda uma parte maior porque o cinco retira só um quinto dos candidatos ao passo que o três retira um terço. Junta um terceiro primo distinto e vai-se outra fração: um número igual a dois vezes três vezes cinco vezes sete guarda menos de um quarto de tudo o que está abaixo. Elevar qualquer desses primos a uma potência maior nada muda — 2 × 3 e 2⁵ × 3⁷ guardam exatamente a mesma proporção. É por isso que a função se descreve pelos primos que dividem n e não pelo tamanho de n.
O teorema que a torna útil
O teorema de Euler diz que elevar qualquer número coprimo com n à potência φ(n) deixa resto um. Esse só facto permite reduzir um expoente antes sequer de o calcular — o expoente só conta módulo φ(n) — e é a dobradiça matemática sobre a qual gira a construção de chave pública padrão. Os expoentes público e privado desse esquema são escolhidos para se multiplicarem a um módulo φ(n), pelo que aplicá-los em sequência devolve a mensagem original. Todo o resto da construção é engenharia; esta é a parte que tem de ser verdadeira.
| n | Fatorização | φ(n) | Parte de n |
|---|---|---|---|
| 36 | 2² × 3² | 12 | 33 % |
| 100 | 2² × 5² | 40 | 40 % |
| 97 | 97 | 96 | 99 % |
Exemplo calculado com a nossa ferramenta
Calculadora da função φ de Euler
Dados
- n (inteiro positivo)
- 36
Resultado
- φ(n)
- 12
- Número de coprimos em 1…n
- 12
Estes números são produzidos pela calculadora abaixo, não escritos à mão — são recalculados sempre que a ferramenta muda.
Refazer com os teus números →Perguntas frequentes
- Porque vale φ(1) um?
- Por convenção, e a convenção ganha o seu lugar. O um conta-se como coprimo consigo próprio porque o seu máximo divisor comum é um, que é a definição empregada, e pôr φ(1) = 1 mantém operacionais todas as fórmulas que usam a função sem caso especial. As definições na fronteira escolhem-se normalmente por essa razão: não porque a resposta seja óbvia, mas porque uma escolha torna verdadeiros os enunciados gerais em toda a parte e a outra mete exceções no texto.
- Pode calcular-se φ(n) sem fatorizar n?
- Por nenhum meio conhecido, e essa ignorância é portante. Conhecer φ(n) para um grande produto de dois primos equivale a conhecer a fatorização — dados ambos, qualquer um produz o outro em duas linhas de álgebra — pelo que um método eficiente para a totiente seria um método eficiente de fatorização. A segurança do esquema de chave pública padrão assenta em ninguém ter nenhum dos dois. É um dos casos mais nítidos em que um pedaço de teoria dos números pura sustenta algo de uso diário.
Artigos que podem interessar-lhe
Todos os guias →Ferramentas relacionadas
Fontes
Detetaste um erro neste artigo?