Calculadora de inverso modular

Um inverso multiplicativo de um inteiro a módulo m é um inteiro x cujo produto com a deixa resto 1 ao ser dividido por m. Em linguagem de congruências, a vezes x é congruente a 1 módulo m. Esta calculadora encontra o menor inverso não negativo pelo algoritmo de Euclides estendido e exibe uma verificação por multiplicação. O módulo deve ser um inteiro maior que um. O inverso existe exatamente quando a e m são coprimos, ou seja, quando seu máximo divisor comum é 1. Se compartilham um fator maior, todo produto que envolve a continua divisível por esse fator módulo m e nunca pode gerar resto 1. Por exemplo, 6 não tem inverso módulo 15 porque o máximo divisor comum é 3. Já 3 tem inverso 4 módulo 11, pois 3 vezes 4 é 12, que deixa resto 1 na divisão por 11. O algoritmo de Euclides estendido faz mais do que calcular o máximo divisor comum. Ele também encontra coeficientes x e y que satisfazem ax mais my igual ao máximo divisor comum. Quando esse divisor é 1, reduzir x módulo m fornece o inverso modular. Se x for negativo, somar cópias suficientes de m o coloca no intervalo padrão de zero a m menos um sem mudar sua classe de congruência. Os inversos modulares substituem a divisão na aritmética modular. A divisão comum não pode ser aplicada diretamente a classes de resíduos porque inteiros diferentes representam o mesmo resíduo. Dividir por a módulo m significa multiplicar pelo inverso de a, desde que ele exista. Essa técnica é fundamental para resolver congruências lineares, simplificar frações modulares, aplicar o teorema chinês dos restos e desenvolver muitos algoritmos de teoria dos números. A criptografia usa inversos modulares amplamente. A geração de chaves RSA calcula o inverso de um expoente módulo um valor relacionado à função totiente de Euler, enquanto cálculos de curvas elípticas usam inversos em fórmulas de pontos sobre corpos finitos. Teoria dos códigos, somas de verificação, geradores pseudoaleatórios e álgebra computacional também dependem de cálculos eficientes de inversos. Implementações criptográficas reais usam rotinas cuidadosamente projetadas de inteiros grandes e tempo constante, em vez da aritmética numérica do navegador, mas a teoria subjacente é a mesma. O inverso é único módulo m, não como inteiro comum. Se 4 é um inverso de 3 módulo 11, então 15, menos 7 e todo número que difere de 4 por um múltiplo de 11 representam o mesmo resíduo inverso. A calculadora informa 4 porque o menor representante não negativo é mais fácil de comparar e reutilizar. Para conferir um resultado, multiplique o inteiro original pelo inverso exibido, divida pelo módulo e verifique se o resto é 1. A mesma regra vale para entradas negativas, pois os resíduos sempre podem ser normalizados para o intervalo padrão. Se a ferramenta indicar que não há inverso, calcule o máximo divisor comum separadamente: qualquer valor acima de 1 comprova o impedimento.