Ir para o conteúdo
OneKitly

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

Daniel Okonkwo — Programador front-end e redator de Tecnologia na OneKitly

Desempenho web · Formatos de ficheiro

Verificado a partir de 2 fontes

Ver perfil →
Em resumo

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.

Publicidade

φ(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)
Como a fatorização comanda a resposta
nFatorizaçãoφ(n)Parte de n
362² × 3²1233 %
1002² × 5²4040 %
97979699 %

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 →
Publicidade

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?