Teorema chinês do resto

O solucionador do teorema chinês do resto recebe um sistema de congruências simultâneas — x congruente a cada resto a_i módulo cada módulo n_i — e retorna a solução única quando ela existe. Você informa arrays paralelos de restos e módulos; o mecanismo os combina com CRT sucessivo, verifica a consistência quando os módulos compartilham fatores, e informa tanto o representante x entre zero e módulo menos um quanto o módulo da classe solução (o produto dos n_i quando eles são coprimos par a par, ou o mínimo múltiplo comum deles caso contrário).

O que o teorema chinês do resto retorna e quando os sistemas falham

O famoso trio de sala de aula — x ≡ 2 mod 3, x ≡ 3 mod 5, x ≡ 2 mod 7 — resulta em x ≡ 23 mod 105. Esta ferramenta também aceita a forma geral: os módulos não precisam ser coprimos par a par. Classicamente, se os módulos são coprimos par a par, existe exatamente uma classe residual módulo o produto dos n_i que satisfaz todas as congruências ao mesmo tempo. Nesse caso, uma solução existe se e somente se cada par de restos concordar módulo o mdc dos módulos correspondentes, e a solução é única módulo o mínimo múltiplo comum de todos os n_i. Quando os restos discordam, a solicitação falha com invalid_input e uma mensagem que nomeia a inconsistência, em vez de inventar um x falso. A resposta em JSON de sucesso inclui x, modulus (o módulo CRT da classe solução), product (o produto bruto dos módulos de entrada), os remainders reduzidos entre zero e n_i menos um, uma cópia dos moduli, e count. Arrays ausentes, comprimentos desiguais, módulos não positivos, não inteiros, e valores fora da faixa de inteiros seguros também falham com invalid_input, para que células ruins de planilha nunca virem respostas erradas silenciosas.

Como os restos e módulos são lidos e como o CRT sucessivo permanece exato

Todo módulo precisa ser um inteiro positivo seguro. Os restos podem ser negativos e são reduzidos para o intervalo canônico antes da combinação. Internamente, o mecanismo começa pela primeira congruência e repetidamente combina a próxima: dado x ≡ x0 mod m e x ≡ a mod n, ele calcula g igual ao mdc de m e n, rejeita o sistema se a menos x0 não for divisível por g, depois constrói a solução atualizada com um inverso modular de m sobre g módulo n sobre g e multiplica o módulo por n sobre g para obter o novo mmc. Todas as multiplicações são protegidas, para que o produto e o módulo CRT intermediário permaneçam dentro dos inteiros seguros do JavaScript; produtos grandes demais falham claramente em vez de dar a volta. Os campos preferidos são remainders e moduli como arrays JSON de inteiros de comprimento igual. Os apelidos a, ai e residues mapeiam para remainders; n, ni e mods mapeiam para moduli, para que formulários, strings de consulta e notebooks legados possam reutilizar um contrato. Cada entrada pode ser um número inteiro JSON ou uma string decimal com um sinal opcional à esquerda; frações, notação científica e espaços incorporados são rejeitados.

Onde os sistemas CRT aparecem no estudo, na intuição de criptografia e no código

Nesta página, o trabalho roda inteiramente no seu navegador; pela API, cada solução bem-sucedida custa US$ 0,002, a validação com falha não é cobrada, e nada é armazenado depois que a resposta é devolvida.