Calculadora da Função Totiente de Euler

Use esta calculadora para informar valores, ajustar opções e analisar resultados em uma área de trabalho compacta e responsiva.

Os resultados são calculados automaticamente conforme você informa os dados.

Número inteiro n Explore n de 1 a 200

A tela inicial apresenta φ(n), a fórmula de fatoração e uma prévia dos resíduos coprimos com n.

Fórmula, resíduos e teorema de Euler

Resultado φ(n) aparece aqui.

Aviso: Todas as ferramentas deste site destinam-se apenas a fins educacionais e informativos. Não constituem aconselhamento profissional. Não há garantia de precisão; verifique unidades, fórmulas, premissas, tolerâncias, arredondamentos e limitações antes de usos importantes. Consulte nossos Termos de Uso.

Premissas e limitações

Os resultados são estimativas educacionais, não aconselhamento profissional de engenharia, construção, segurança, ciência, direito, finanças ou área acadêmica. Não há garantia de que as saídas sejam precisas, completas, adequadas ou livres de erros. Verifique unidades, fórmulas, premissas, tolerâncias, arredondamentos e limitações de forma independente e conte com a revisão de profissionais qualificados em trabalhos técnicos ou sensíveis à segurança. Esta calculadora destina-se apenas à exploração educacional da teoria dos números. Ela não é uma ferramenta criptográfica, gerador de chaves ou validador de segurança. Não use os resultados para parâmetros de segurança reais, registros oficiais ou decisões de alto impacto sem uma revisão qualificada. O uso desta calculadora está sujeito aos nossos Termos de Uso.

▼ Veja explicações e dicas abaixo ▼

Calculadoras relacionadas

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

A função totiente de Euler, escrita como $\varphi(n)$, conta quantos inteiros são coprimos com um inteiro positivo $n$. Dois inteiros são coprimos quando seu máximo divisor comum é $1$.

Por exemplo, os inteiros positivos até $12$ que são coprimos com $12$ são:

$$ 1,\ 5,\ 7,\ 11 $$

Nenhum deles tem um fator comum com $12$ além de $1$, portanto:

$$ \varphi(12)=4 $$

A função totiente é útil porque conecta fatoração em primos, aritmética modular, resíduos reduzidos, o teorema de Euler e a aritmética no estilo RSA. Em vez de perguntar apenas “o que divide $n$?”, ela pergunta “quantos resíduos continuam utilizáveis quando removemos os números que compartilham fatores com $n$?”

Uma definição comum é:

$$ \varphi(n)=\#\left\{a:1\le a\le n,\ \gcd(a,n)=1\right\} $$

Em outras palavras: $\varphi(n)$ é a quantidade de inteiros de $1$ a $n$ cujo máximo divisor comum com $n$ é $1$. Para $n>1$, isso equivale a contar os resíduos reduzidos de $1$ a $n-1$.

Por que a função totiente de Euler é importante

A função totiente de Euler é importante porque transforma um problema de contagem em um problema de estrutura. A princípio, $\varphi(n)$ parece ser algo que você encontraria verificando todos os números de $1$ a $n$. Mas, quando você conhece a fatoração em primos de $n$, pode calcular $\varphi(n)$ diretamente.

Isso é importante na teoria dos números porque muitos resultados de aritmética modular dependem de resíduos coprimos. Por exemplo, o teorema de Euler diz que, se $a$ é coprimo com $n$, então:

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

Esse teorema generaliza o pequeno teorema de Fermat, passando de módulos primos para muitos módulos compostos. A mesma família de ideias também aparece em explicações introdutórias da aritmética no estilo RSA, nas quais um módulo costuma ser escrito como o produto de dois primos distintos.

Termos importantes

Inteiro: Um número sem parte fracionária, como $1$, $8$, $33$ ou $1000000$.
Inteiro positivo: Um inteiro maior que $0$.
Máximo divisor comum: O maior inteiro positivo que divide dois números. Ele costuma ser escrito como $\gcd(a,b)$.
Inteiros coprimos: Dois inteiros cujo máximo divisor comum é $1$.
Número primo: Um inteiro maior que $1$ cujos únicos divisores positivos são $1$ e ele mesmo.
Número composto: Um inteiro maior que $1$ que não é primo.
Fatoração em primos: Escrever um número como produto de potências de primos, como $72=2^3\cdot 3^2$.
Resíduo reduzido: Um resíduo módulo $n$ que é coprimo com $n$.
Sistema de resíduos reduzidos: Um conjunto completo de resíduos reduzidos incongruentes módulo $n$.
Aritmética modular: Aritmética baseada nos restos após a divisão por um módulo.

Como funciona a função totiente de Euler

A maneira direta de encontrar $\varphi(n)$ é testar cada número de $1$ a $n$ e contar os valores cujo máximo divisor comum é $1$ com $n$. Esse método é fácil de entender, mas não é a maneira mais eficiente de calcular a função.

O método mais rápido usa os fatores primos distintos de $n$. Se $p$ percorre os números primos distintos que dividem $n$, então:

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

Em que:

$n$ é o inteiro positivo que está sendo avaliado.
$p\mid n$ significa que $p$ é um divisor primo de $n$.
O produto usa cada fator primo distinto uma vez, mesmo quando esse primo aparece com um expoente.

Essa fórmula funciona porque cada fator primo de $n$ remove uma fração previsível dos resíduos. Se $2$ divide $n$, então os múltiplos de $2$ não são coprimos com $n$. Se $3$ também divide $n$, os múltiplos de $3$ também são excluídos. A fórmula do produto combina essas exclusões de modo a evitar a contagem dupla.

Se a fatoração em primos for:

$$ n=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r} $$

então a função totiente também pode ser escrita como:

$$ \varphi(n)=\prod_{i=1}^{r}p_i^{e_i-1}(p_i-1) $$

As duas formas dão o mesmo resultado. A forma do produto com $n\prod(1-1/p)$ costuma ser a mais fácil de aplicar quando os fatores primos distintos são conhecidos.

Exemplos práticos da função totiente de Euler

Exemplo 1: contando os valores coprimos com $12$

Comece com os números de $1$ a $12$:

$$ 1,2,3,4,5,6,7,8,9,10,11,12 $$

Mantenha apenas os números cujo máximo divisor comum com $12$ é $1$:

$$ 1,5,7,11 $$

Há $4$ números assim, portanto:

$$ \varphi(12)=4 $$

Agora confira o mesmo valor usando a fórmula da fatoração em primos. Como:

$$ 12=2^2\cdot 3 $$

usamos os fatores primos distintos $2$ e $3$:

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

$$ \varphi(12)=12\cdot\frac{1}{2}\cdot\frac{2}{3}=4 $$

Exemplo 2: um número primo

Se $n$ for primo, todo inteiro positivo menor que $n$ seria coprimo com $n$. Para $n=13$, os valores coprimos são:

$$ 1,2,3,4,5,6,7,8,9,10,11,12 $$

Há $12$ valores, portanto:

$$ \varphi(13)=12 $$

Para qualquer primo $p$:

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

É por isso que os valores primos ficam sobre a linha $\varphi(n)=n-1$ em um gráfico de tendência da função totiente.

Exemplo 3: uma potência de primo

Para $n=8$, a fatoração em primos é:

$$ 8=2^3 $$

Usando a fórmula do produto:

$$ \varphi(8)=8\left(1-\frac{1}{2}\right)=4 $$

Os resíduos reduzidos são:

$$ 1,3,5,7 $$

Embora $8$ tenha apenas um fator primo distinto, esse fator primo ainda remove todos os resíduos pares.

Exemplo 4: um semiprimo e o atalho no estilo RSA

Um semiprimo é o produto de dois primos. Se $n$ for o produto de dois primos distintos, $p$ e $q$, então:

$$ n=pq $$

e a função totiente se torna:

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

Por exemplo, seja:

$$ n=33=3\cdot 11 $$

Então:

$$ \varphi(33)=(3-1)(11-1)=2\cdot 10=20 $$

Esse atalho funciona para produtos de dois primos distintos. Ele não deve ser usado sem alterações quando $n$ não tiver a forma $pq$ com fatores primos distintos.

Exemplo 5: o caso especial $n=1$

Convencionalmente, o valor $\varphi(1)$ é considerado:

$$ \varphi(1)=1 $$

Esse caso é especial porque não há inteiros positivos menores que $1$. Na aritmética modular, o módulo $1$ também se comporta de forma diferente dos módulos comuns, pois todo inteiro é congruente a $0$ módulo $1$. Nos resultados da calculadora, trate $n=1$ como uma convenção especial, e não como um exemplo típico de contagem.

Como interpretar o resultado

O resultado principal $\varphi(n)$ é uma contagem. Ele informa quantos resíduos são coprimos com $n$.

Um valor maior de $\varphi(n)$ significa que mais resíduos continuam utilizáveis módulo $n$. Um valor menor significa que mais resíduos compartilham fatores com $n$ e são excluídos do sistema de resíduos reduzidos.

Para um primo $n$, o resultado é o maior possível para $n>1$:

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

Para um $n>1$ composto, o resultado é menor porque pelo menos alguns valores compartilham um fator não trivial com $n$.

Item do resultado	O que significa
$\varphi(n)$	A quantidade de resíduos coprimos com $n$
Fatoração em primos	As potências de primos usadas para calcular a função totiente
Contagem de coprimos	Outra forma de descrever o mesmo total contado por $\varphi(n)$
Resíduos reduzidos	Valores coprimos com $n$, exibidos como uma prévia quando a lista é longa
Fórmula do produto	A substituição dos fatores primos na fórmula da função totiente
Etiquetas	Rótulos do tipo de número, como primo, potência de primo, livre de quadrados ou composto
Gráfico de tendência	Uma comparação visual dos valores de $\varphi(n)$ entre inteiros próximos
Exemplo do teorema de Euler	Um exemplo de exponenciação modular usando uma base coprima selecionada automaticamente
Conexão com RSA	Um recurso auxiliar para a fórmula de semiprimos quando a fatoração tem exatamente dois fatores primos distintos

A prévia dos resíduos reduzidos é especialmente útil para valores pequenos de $n$, nos quais é fácil inspecionar a lista completa. Para valores maiores, a prévia pode mostrar apenas a primeira parte do sistema de resíduos reduzidos, portanto os itens exibidos na tela podem não formar a lista completa.

O gráfico de tendência ajuda a explicar o formato da função totiente. Os números primos aparecem no envelope superior $\varphi(n)=n-1$. Os números compostos geralmente aparecem abaixo dessa linha porque pelo menos um fator não trivial remove resíduos adicionais da contagem.

Erros comuns e equívocos

Um erro comum é confundir $\varphi(n)$ com a quantidade de divisores de $n$. Essas são perguntas diferentes. A função totiente conta os números que são coprimos com $n$; a função que conta divisores conta os números que dividem $n$.

Por exemplo, $12$ tem $6$ divisores positivos:

$$ 1,2,3,4,6,12 $$

Mas $\varphi(12)=4$, pois apenas:

$$ 1,5,7,11 $$

são coprimos com $12$.

Outro erro é aplicar o atalho no estilo RSA de forma ampla demais. A fórmula:

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

é válida para dois primos distintos, $p$ e $q$. Ela não é o atalho adequado para uma potência de primo como $p^2$, nem para um número com três ou mais fatores primos distintos.

Às vezes, os usuários também esperam que a prévia de resíduos reduzidos liste todos os resíduos. Para valores grandes de $\varphi(n)$, a prévia pode ser limitada, portanto deve ser lida como uma amostra dos resíduos reduzidos, e não como uma lista completa.

Também é fácil esquecer que a entrada deve ser um inteiro positivo. Zero, números negativos, decimais, entradas vazias e entradas não numéricas não se encaixam na definição usada aqui.

Por fim, o cartão do teorema de Euler deve ser lido como um exemplo, não como uma prova completa para toda base. O teorema de Euler se aplica quando a base é coprima com $n$, mas a calculadora escolhe automaticamente uma base coprima pequena, em vez de permitir que o usuário teste todas as bases possíveis.

Quando usar a função totiente de Euler

Use a função totiente de Euler quando precisar entender quantos resíduos são coprimos com um módulo.

Usos comuns incluem:

Estudar aritmética modular.
Encontrar o tamanho de um sistema de resíduos reduzidos módulo $n$.
Aplicar o teorema de Euler.
Comparar o comportamento de primos e compostos na teoria dos números.
Resolver exemplos introdutórios no estilo RSA com módulos semiprimos.
Entender como a fatoração em primos afeta a aritmética módulo $n$.

A função é especialmente útil quando um problema envolve a expressão “primo relativo a $n$” ou “invertível módulo $n$”.

Limitações e pontos importantes

O resultado matemático principal é exato para as entradas aceitas. É uma contagem inteira, não uma estimativa ou um decimal arredondado.

A calculadora aceita inteiros positivos formados apenas por algarismos decimais até $1,000,000$. Valores acima desse limite não são aceitos para que o cálculo continue responsivo. Decimais, sinais e notação científica são inválidos, em vez de serem convertidos em um inteiro próximo.

O controle deslizante de tendência usa valores inteiros e é limitado a um intervalo gráfico de $20$ a $200$. Mover o controle também seleciona o valor correspondente de $n$, portanto ele altera o cálculo, e não apenas a exibição do gráfico.

A lista de resíduos reduzidos é uma prévia quando fica longa. Se houver mais de $80$ resíduos disponíveis, apenas a primeira parte será exibida.

A etiqueta de altamente composto é verificada apenas para valores até $1,000$. Para entradas aceitas maiores, o resultado informa explicitamente que essa classificação não foi avaliada.

O cartão de conexão com RSA é educativo. Ele mostra a fórmula direta de semiprimos somente quando $n$ tem exatamente dois fatores primos distintos. Esta calculadora não é um gerador de chaves criptográficas e não deve ser usada para criar parâmetros reais de segurança.

O exemplo do teorema de Euler usa uma base coprima escolhida automaticamente. Ele é útil para ver o teorema em ação, mas não é uma ferramenta de exponenciação modular escolhida pelo usuário.

Como usar esta calculadora

Digite um inteiro positivo $n$.
Se quiser, use o controle deslizante de tendência ou clique em um ponto do gráfico para selecionar um valor gráfico compatível.
Leia o resultado principal de $\varphi(n)$.
Consulte a fatoração em primos e a fórmula do produto para ver como o resultado foi calculado.
Confira a contagem de coprimos, a prévia de resíduos reduzidos e as etiquetas de tipo de número.
Use o gráfico de tendência para comparar $\varphi(n)$ com valores próximos.
Consulte os cartões do teorema de Euler e da conexão com RSA como recursos de interpretação.
Baixe o gráfico como PNG se precisar de uma cópia visual.

Perguntas frequentes

O que $\varphi(n)$ conta?

$\varphi(n)$ conta quantos inteiros de $1$ a $n$ são coprimos com $n$. Para $n>1$, isso equivale a contar os resíduos de $1$ a $n-1$ cujo máximo divisor comum é $1$ com $n$.

Por que $\varphi(p)=p-1$ quando $p$ é primo?

Se $p$ for primo, nenhum dos inteiros $1,2,\ldots,p-1$ é divisível por $p$. Portanto, cada um deles é coprimo com $p$, e há $p-1$ valores coprimos.

Por que a fatoração em primos ajuda a calcular a função totiente?

Os fatores primos mostram exatamente quais resíduos devem ser excluídos porque compartilham um fator com $n$. A fórmula do produto usa cada fator primo distinto para remover a fração correta dos resíduos não coprimos.

$\varphi(n)$ é igual à quantidade de divisores de $n$?

Não. $\varphi(n)$ conta os valores que são coprimos com $n$, enquanto a contagem de divisores mede quantos inteiros positivos dividem $n$. Por exemplo, $12$ tem $6$ divisores positivos, mas $\varphi(12)=4$.

O que é um sistema de resíduos reduzidos?

Um sistema de resíduos reduzidos módulo $n$ é um conjunto completo de resíduos coprimos com $n$, sem que dois valores representem a mesma classe de resíduos módulo $n$. Seu tamanho é $\varphi(n)$.

Como o teorema de Euler usa $\varphi(n)$?

O teorema de Euler diz que, se $a$ é coprimo com $n$, então:

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

Isso significa que a função totiente fornece um expoente que leva uma base coprima de volta a $1$ módulo $n$.

Por que a calculadora rejeita decimais, zero e números negativos?

A função totiente de Euler, neste contexto, é definida para inteiros positivos. Decimais, zero e valores negativos não correspondem a esse domínio de entrada, portanto não são aceitos.

Por que a lista de resíduos às vezes fica incompleta?

Para valores grandes, a quantidade de resíduos reduzidos pode ser alta. A calculadora mostra uma prévia dos primeiros resíduos e indica quando não está exibindo a lista completa.

Quando posso usar $\varphi(pq)=(p-1)(q-1)$?

Use esse atalho quando $p$ e $q$ forem primos distintos e $n=pq$. Para outras fatorações, use a fórmula geral do produto.

Fontes e referências

Livros e livros didáticos

William Stein. Elementary Number Theory: Primes, Congruences, and Secrets. Versão de 23 de janeiro de 2017. Seções relevantes usadas: Capítulo 1, Seção 1.1, sobre fatoração em primos; Capítulo 2, Seção 2.1.2, sobre o teorema de Euler e a função $\varphi$ de Euler; Capítulo 2, Seção 2.2.1, sobre multiplicatividade e o cálculo de $\varphi(n)$ a partir de potências de primos. https://wstein.org/ent/ent.pdf
Jonathan A. Poritz. Yet Another Introductory Number Theory Textbook – Cryptology Emphasis. Mathematics LibreTexts, “2.5: Euler’s $\phi$ Function”, última atualização em 18 de julho de 2021. Material relevante usado: definição da função totiente de Euler, resíduos invertíveis módulo $n$ e multiplicatividade para entradas primas entre si. https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Yet_Another_Introductory_Number_Theory_Textbook_-_Cryptology_Emphasis_(Poritz)/02%3A_Congruences/2.05%3A_Euler's__%CF%95__Function

Fontes acadêmicas e primárias

R. L. Rivest, A. Shamir e L. Adleman. “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems.” Communications of the ACM, 21(2), 1978. Material relevante usado: o uso de um módulo $n=pq$ no estilo RSA, exponenciação modular e a relação com $(p-1)(q-1)$. https://people.csail.mit.edu/rivest/Rsapaper.pdf