Verificador de coprimos

O verificador de coprimos responde a uma pergunta básica de teoria dos números: dois inteiros compartilham apenas o um como divisor positivo comum? Informe os inteiros a e b e a ferramenta retorna tanto o máximo divisor comum quanto um sinalizador booleano coprime que é true exatamente quando esse mdc é igual a um. O mecanismo usa o algoritmo de Euclides clássico sobre valores absolutos, então o resultado é exato, determinístico, e livre de desvio de ponto flutuante. Ele nunca chama a rede, nunca amostra aleatoriedade, e nunca depende do relógio.

O que significa coprimo e o que a resposta contém

Dois inteiros são coprimos, ou primos entre si, quando seu único divisor comum positivo é um. De forma equivalente, o mdc de a e b é igual a um. Exemplos clássicos incluem oito e quinze, cujos divisores não se sobrepõem além do um, e catorze e vinte e um, que compartilham sete.

Este verificador retorna os inteiros originais a e b conforme interpretados, o mdc positivo, e um campo booleano coprime que é true se e somente se esse mdc for exatamente um. O caso especial de a igual a zero e b igual a zero é rejeitado porque o mdc de zero e zero é indefinido neste contexto e a coprimalidade não pode ser decidida. Em contraste, zero e cinco é válido: o mdc é cinco e coprime é false.

Entradas negativas são permitidas e são reduzidas via valores absolutos, correspondendo à convenção matemática usual de que o mdc é não negativo. Se você precisar de fatores primos de um único inteiro, em vez de um teste de mdc par a par, use uma ferramenta de fatoração; esta página responde apenas à pergunta de coprimalidade e mdc de dois inteiros.

Como as entradas são lidas e como o mdc de Euclides permanece exato

Sinais opcionais de mais ou menos à esquerda são permitidos; espaços incorporados, prefixos hexadecimais e notação exponencial são rejeitados, para que uma célula ruim não vire um sinalizador errado. O mecanismo permanece dentro dos inteiros seguros do JavaScript, o que é mais que suficiente para problemas de sala de aula, concursos de programação, e a maioria das verificações aplicadas em inversos modulares ou razões simplificadas.

Internamente, os valores absolutos são alimentados ao algoritmo de Euclides: substitua repetidamente o par pelo maior e o resto, até que o resto seja zero, então o último resto não nulo é o mdc. Esse procedimento tem séculos, precisa de apenas algumas divisões para entradas comuns, e nunca aproxima. Não há passo em ponto flutuante que pudesse arredondar um quase-inteiro em uma falsa afirmação de coprimalidade.

Onde as verificações de coprimalidade se encaixam no estudo, na intuição de criptografia e no código

Estudantes encontram pares coprimos ao reduzir frações, ao provar que o totiente de Euler conta inteiros até n que são coprimos com n, e quando um inverso modular existe precisamente porque o coeficiente e o módulo são coprimos. Professores podem gerar gabaritos para planilhas de exercícios sem confiar em aplicativos de calculadora opacos que escondem o mdc.

Desenvolvedores usam o mesmo contrato para validar que dois valores de semente são primos entre si antes de construir um gerador congruencial linear, para verificar previamente relações estilo RSA entre e e phi em demonstrações educacionais, ou para condicionar um passo de normalização de fração em pipelines de dados. A prática de concursos costuma precisar de uma fonte rápida e offline de respostas de mdc e coprimalidade, para que soluções possam ser verificadas sem baixar tabelas.

Combine-a com fatoração em primos quando precisar das potências primas por trás de um único inteiro, e com uma ferramenta de enésimo primo quando precisar de posições em vez de divisores par a par.