Calculadora da Função Totiente de Euler

Bem-vindo à Calculadora da Função Totiente de Euler, uma ferramenta abrangente de teoria dos números que calcula φ(n) (função phi de Euler) com fatoração prima passo a passo, visualização interativa em grade de números coprimos e análise detalhada. Esteja você estudando álgebra abstrata, preparando-se para competições de matemática, trabalhando em criptografia RSA ou explorando aritmética modular, esta calculadora oferece computação de nível profissional com rico conteúdo educacional.

O que é a Função Totiente de Euler?

A função totiente de Euler φ(n), também conhecida como função phi de Euler, conta o número de inteiros positivos de 1 a n que são relativamente primos (coprimos) a n. Dois números são coprimos quando o seu máximo divisor comum (MDC) é igual a 1.

Por exemplo, φ(12) = 4 porque exatamente quatro números — 1, 5, 7 e 11 — são coprimos de 12 entre os inteiros de 1 a 12.

A Fórmula do Produto

A maneira mais eficiente de calcular φ(n) utiliza a fatoração prima de n. Se \(n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}\), então:

Isso significa que multiplicamos n por \((1 - 1/p)\) para cada fator primo distinto p de n. Os expoentes não importam — apenas os primos distintos.

Principais Propriedades

Teorema de Euler

O teorema de Euler é o resultado fundamental que torna a função totiente crucial na criptografia:

Isso generaliza o pequeno teorema de Fermat (que é o caso especial quando n é primo). Ele forma a base matemática da criptografia RSA.

Como Usar Esta Calculadora

1. Insira um inteiro positivo: Digite qualquer valor de 1 a 1.000.000 no campo de entrada.
2. Use exemplos rápidos: Clique nos botões de exemplo para testar valores clássicos como primos, números compostos ou semiprimos do estilo RSA.
3. Veja seus resultados: A calculadora mostra φ(n), fatoração prima, razão coprima e propriedades detectadas.
4. Explore a grade coprima: Para n ≤ 400, veja quais números são coprimos de n em uma grade visual animada.
5. Estude o gráfico de tendência: Veja como φ(k) varia para k = 1 até o mínimo(n, 100).

Conexão com Criptografia RSA

Na criptografia RSA, a função totiente de Euler desempenha um papel central:

1. Escolha dois primos grandes p e q. Calcule n = p × q.
2. Calcule φ(n) = (p−1)(q−1).
3. Escolha o expoente público e com mdc(e, φ(n)) = 1.
4. Calcule o expoente privado d tal que e × d ≡ 1 (mod φ(n)).

A segurança do RSA depende da dificuldade de calcular φ(n) sem conhecer a fatoração de n. Se um invasor pudesse calcular φ(n) de forma eficiente, ele poderia quebrar o RSA.

Valores Comuns de φ(n)

Perguntas Frequentes

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

A função totiente de Euler φ(n), também chamada de função phi de Euler, conta o número de inteiros positivos de 1 a n que são relativamente primos (coprimos) a n. Dois números são coprimos quando seu máximo divisor comum (MDC) é 1. Por exemplo, φ(12) = 4 porque apenas 1, 5, 7 e 11 são coprimos de 12.

Como calcular a função totiente de Euler?

Para calcular φ(n): (1) Encontre a fatoração prima de n. (2) Aplique a fórmula do produto: φ(n) = n × ∏(1 − 1/p) para cada fator primo distinto p de n. Por exemplo, φ(12) = 12 × (1−1/2) × (1−1/3) = 12 × 1/2 × 2/3 = 4. Para um primo p, φ(p) = p−1. Para uma potência de primo p^k, φ(p^k) = p^k − p^(k−1).

Por que a função totiente de Euler é importante na criptografia RSA?

Na criptografia RSA, o módulo n = p × q é o produto de dois primos grandes. O totiente φ(n) = (p−1)(q−1) é usado para computar a chave privada: o expoente de descriptografia d deve satisfazer e × d ≡ 1 (mod φ(n)), onde e é o expoente de criptografia público. Sem saber φ(n) — o que requer a fatoração de n — computar d é computacionalmente inviável.

O que é o teorema de Euler e como ele se relaciona com a função totiente?

O teorema de Euler afirma que se a e n são coprimos, então a^φ(n) ≡ 1 (mod n). Esta é uma generalização do pequeno teorema de Fermat (que se aplica quando n é primo). É fundamental na aritmética modular e criptografia, fornecendo a base matemática para a criptografia RSA e exponenciação modular eficiente.

Quais são as principais propriedades da função totiente de Euler?

As principais propriedades incluem: (1) φ(1) = 1. (2) Para primo p: φ(p) = p−1. (3) Para potência de primo p^k: φ(p^k) = p^(k−1)(p−1). (4) Propriedade multiplicativa: se mdc(m,n) = 1, então φ(m×n) = φ(m)×φ(n). (5) Soma sobre divisores: Σ φ(d) = n para todos os divisores d de n. (6) φ(n) é sempre par para n > 2.

O que significa dois números serem coprimos?

Dois inteiros a e b são coprimos (também chamados de relativamente primos) se o seu máximo divisor comum for 1, significando que não compartilham fatores primos comuns. Por exemplo, 8 e 15 são coprimos porque mdc(8,15) = 1, embora nenhum deles seja primo. A função totiente φ(n) conta exatamente quantos inteiros de 1 a n são coprimos de n.