Calculadora de Aritmética Modular (Calculadora de Mod)
Calculadora de aritmética modular com 4 modos: mod básico, soma/subtração/multiplicação modular, exponenciação modular (exponenciação rápida por quadrados sucessivos) e inverso modular (algoritmo de Euclides estendido). Calcula com precisão o mod de números negativos e expoentes enormes usando BigInt.
Propriedades básicas da aritmética modular
| Propriedade | Descrição |
|---|---|
| (a + b) mod n = ((a mod n) + (b mod n)) mod n | O resultado é o mesmo, quer se tire o mod antes ou depois da soma. |
| (a − b) mod n = ((a mod n) − (b mod n) + n) mod n | Como a subtração pode resultar em um valor negativo, somar n no final e tirar o mod n novamente mantém o resultado dentro do intervalo [0, n). |
| (a × b) mod n = ((a mod n) × (b mod n)) mod n | Assim como na soma, tirar o mod durante a multiplicação não altera o resultado final. Essa propriedade é a base do cálculo rápido da exponenciação (quadrados sucessivos). |
| a e n são coprimos ⇔ existe um inverso de a módulo n | Só quando o algoritmo de Euclides estendido resulta em gcd(a, n) = 1 existe um x (o inverso) que satisfaz a × x ≡ 1 (mod n). |
Dicas
- O comportamento do mod com números negativos varia conforme a linguagem de programação. Esta ferramenta segue a definição matemática (o resultado está sempre entre 0 e n − 1), portanto -7 mod 3 resulta em 2, e não em -1.
- O modo de exponenciação usa o método de quadrados sucessivos, por isso retorna resultados instantaneamente mesmo quando o expoente tem centenas de dígitos. O mesmo algoritmo é usado na criptografia e decriptografia RSA.
- O horário do relógio é um exemplo do dia a dia de aritmética modular: ao converter "15h" para o formato de 12 horas, obtemos 15 mod 12 = 3 horas.
- O modo de inverso funciona desde que a e n sejam coprimos (o máximo divisor comum seja 1), mesmo que n não seja primo.
- Na programação competitiva, é comum que os problemas peçam a resposta módulo um número primo grande, como 1.000.000.007, em vez do número gigante bruto. O modo de exponenciação desta ferramenta também é útil para conferir esse tipo de cálculo manualmente.
Perguntas frequentes
Curiosidade — a "aritmética do relógio" por trás da criptografia moderna
A aritmética modular (congruência) costuma ser chamada de "aritmética do relógio" (clock arithmetic). Em um relógio de 12 horas, 13h é tratado como "igual" a 1h — isso é exatamente a congruência 13 ≡ 1 (mod 12), uma ideia que se concentra apenas no resto da divisão de um número por um módulo (neste caso, 12). O matemático alemão Carl Friedrich Gauss sistematizou a notação "≡" para congruência em seu livro de 1801, Disquisitiones Arithmeticae, transformando essa ideia em uma ferramenta padrão da matemática moderna.
Essa operação aparentemente simples sustenta os alicerces da segurança moderna da internet. Em sistemas de chave pública como o RSA, a "exponenciação modular" — calcular a potência de um número enorme e depois tirar o resto módulo n — é a operação central da criptografia e da decriptografia. Como o expoente e o módulo podem ter centenas de dígitos cada, calcular ingenuamente a potência completa antes de tirar o resto tornaria o cálculo explosivo. Já os quadrados sucessivos exigem apenas um número de multiplicações proporcional ao número de dígitos do expoente, tornando o processo viável na prática.
O cálculo de inversos modulares pelo algoritmo de Euclides estendido também é uma técnica fundamental usada em diversas áreas da ciência da computação, da criptografia à teoria de códigos e ao design de funções hash. O fato de uma "aritmética com mais de 2.000 anos" e a "tecnologia de segurança mais avançada" se apoiarem no mesmo fundamento matemático é um símbolo marcante da universalidade da teoria dos números.