Calculadora do teorema chinês do resto

O teorema chinês do resto, frequentemente abreviado como CRT em inglês, combina várias condições modulares em uma solução. Uma congruência como x ≡ 2 módulo 3 significa que dividir x por 3 deixa resto 2. Esta calculadora aceita três equações desse tipo e encontra o menor inteiro não negativo que satisfaz todas simultaneamente. O teorema clássico se aplica quando os módulos são coprimos dois a dois, ou seja, cada par tem máximo divisor comum igual a um. Nessa condição, há exatamente uma solução módulo o produto dos módulos. Para os módulos 3, 5 e 7, o produto é 105. Se a menor solução for 23, então 23, 128, 233 e todos os números obtidos somando ou subtraindo 105 satisfazem o mesmo sistema. O algoritmo construtivo começa multiplicando todos os módulos para formar M. Para cada equação, divide M pelo módulo correspondente e obtém um produto parcial. Como os módulos são coprimos dois a dois, o produto parcial tem um inverso multiplicativo modular em relação ao módulo omitido. Multiplicar cada resto, produto parcial e inverso cria um termo que atende a uma congruência e contribui com zero para as demais. Somar os termos e reduzir módulo M fornece a resposta. O CRT tem aplicações muito além da teoria dos números dos livros. Ele permite aritmética eficiente com inteiros grandes e é usado em implementações criptográficas, teoria de códigos, ciclos de calendário, escalas de revezamento, álgebra computacional e reconstrução de valores a partir de resíduos. É especialmente útil quando um cálculo difícil pode ser dividido em cálculos menores e independentes módulo vários números e recombinado depois. Insira restos inteiros e módulos maiores que um. O resto pode ser negativo ou maior que seu módulo, pois a redução o normaliza automaticamente. Esta versão exige intencionalmente módulos coprimos dois a dois, seguindo o teorema padrão e garantindo uma classe de resíduos única. Sistemas com módulos não coprimos às vezes têm solução, mas exigem uma verificação adicional de compatibilidade e estão fora do escopo desta calculadora. Sempre confira o resultado dividindo-o por cada módulo e verificando o resto.