A função tociente de Euler, escrita φ(n), conta quantos inteiros positivos até n não compartilham nenhum fator comum com n. Parece um simples exercício de contagem, mas sustenta a aritmética modular, a generalização de Euler do pequeno teorema de Fermat e a etapa de geração de chaves da criptografia RSA. Esta calculadora calcula φ(n) por meio de fatoração primária, mostra a derivação passo a passo e - para n pequeno - lista cada número inteiro coprimo diretamente.
O que φ(n) realmente conta
φ(n) conta os inteiros positivos k no intervalo 1 ≤ k ≤ n para o qual mdc(k, n) = 1 — ou seja, k e n são coprimos. Para n = 1, φ(1) = 1 por convenção. Para um p primo, cada número inteiro abaixo dele é automaticamente coprimo, então φ(p) = p − 1. A guia Lista Coprime desta calculadora lista esses números inteiros diretamente sempre que n é pequeno o suficiente (até 2.000) para exibi-los todos.
Como a fatoração primária fornece a fórmula
A maneira mais rápida de calcular φ(n) para um n grande não é verificar a coprimalidade de cada número inteiro — é fatorar primo n primeiro. O tociente de Euler é uma função multiplicativa, significando φ(mn) = φ(m)φ(n) sempre que mdc(m, n) = 1. Combinado com o fato de que φ(p^k) = p^k − p^(k-1) = p^k(1 − 1/p) para qualquer potência principal, isso dá a fórmula geral φ(n) = n·Π(1 − 1/p) sobre cada fator primo distinto p de n — os próprios expoentes desaparecem completamente da fórmula. A guia Fatoração Primária desta calculadora mostra exatamente essa derivação, termo por termo, para qualquer n que você inserir.
Por que a criptografia se preocupa com φ(n)
A criptografia RSA gera um par de chaves pública/privada a partir de dois grandes primos distintos p e q, sendo n = pq o módulo público. O expoente privado é derivado usando φ(n) = (p−1)(q−1) — a mesma fórmula que a linha de interpretação desta calculadora destaca sempre que n fatora exatamente dois primos distintos. Em implementações reais de RSA, p e q têm centenas de dígitos, mas o cálculo do totiente subjacente é idêntico ao mostrado aqui para pequenos exemplos. Ferramentas relacionadas, como a Calculadora de Fatoração Primária e a Calculadora de Módulo são úteis para explorar os outros blocos de construção da teoria dos números por trás da aritmética modular e da criptografia.