Elysia Tools
Navegação
Math & Numbers
Calcula o símbolo de Jacobi (a/n) (n ímpar até 10¹⁸; Legendre se n for primo): módulo um primo, a^((n−1)/2) ≡ 1 indica resíduo quadrático e Tonelli–Shanks (ou a fórmula direta se p ≡ 3 (mod 4)) fornece as raízes ±√a; o símbolo −1 certifica que a NÃO é resíduo. Com módulo composto o símbolo é só necessário: −1 prova não-resíduo e +1 é inconclusivo (resolvido por força bruta quando n ≤ 10⁵). Clássico: 10 é resíduo quadrático mod 13 com raízes ±6.
Execução
Preencha o formulário, execute a ferramenta e veja o resultado no mesmo lugar.
Exemplos
Relacionado
Guia de uso da ferramenta
O Verificador de Resíduo Quadrático calcula os símbolos de Legendre e Jacobi para determinar se um número inteiro é um resíduo quadrático módulo n. A ferramenta executa o teste de primalidade determinístico de Miller–Rabin no módulo, avalia o critério de Euler e calcula as raízes quadradas modulares pelo algoritmo de Tonelli–Shanks quando o módulo é primo.
Contexto
Precisa resolver a congruência x² ≡ 10 (mod 13) para um trabalho de criptografia.
Problema
Saber se 10 é resíduo quadrático módulo 13 e encontrar os valores de x.
Como usar
Insira 10 no campo 'Valor a', 13 no campo 'Módulo n' e marque a opção para resolver raízes.
Resultado
O Legendre resulta em +1 e as raízes encontradas e verificadas são 6 e 7.
Contexto
Analisando propriedades de resíduos quadráticos com módulos compostos ímpares.
Problema
Verificar se 2 é resíduo quadrático módulo 15, onde o símbolo de Jacobi resulta em +1.
Como usar
Insira 2 no campo 'Valor a', 15 no campo 'Módulo n' e execute a verificação.
Resultado
O Jacobi resulta em +1, mas a verificação exaustiva determina que 2 não possui raiz módulo 15.
O símbolo de Legendre é definido estritamente para módulos primos, enquanto o símbolo de Jacobi generaliza o conceito para qualquer módulo ímpar composto.
Não. Para módulos compostos, Jacobi igual a +1 é inconclusivo; apenas o valor −1 garante que o número não é resíduo quadrático.
O módulo ímpar n suporta valores de 3 até 10¹⁸, enquanto o valor a aceita inteiros de até 10⁵¹².
Para módulos primos, a ferramenta usa Tonelli–Shanks ou a fórmula direta quando p ≡ 3 (mod 4).
Não, o módulo n deve ser um número ímpar maior ou igual a 3.