Verificador de resíduo quadrático
Diz se um número tem raiz quadrada módulo m e lista todas as raízes: 2 é um quadrado módulo 7, porque 3 ao quadrado é 9, que deixa 2, e as raízes são 3 e 4. Grátis no seu navegador.
- Grátis
- Funciona no seu navegador
- Sem cadastro
- Seus dados não saem do seu aparelho
Executar grátis
Exemplo resolvido
- A
- 2
- Módulo m
- 7
- A mód
- 2
- Raízes
- 3, 4
- Núm. de raízes
- 2
Um inteiro a é resíduo quadrático módulo m quando algum inteiro x satisfaz x ao quadrado congruente a a módulo m — em outras palavras, a tem uma raiz quadrada modular. Essa pergunta de sim ou não aparece em lições de criptografia, teoria dos números de competição e qualquer fluxo que precise saber se uma congruência é um quadrado perfeito antes de gastar esforço em um solucionador maior. Esta capacidade recebe a e um módulo m (pelo menos dois), reduz a ao intervalo canônico de zero até m menos um, busca cada raiz nesse intervalo e pode opcionalmente devolver a lista completa de classes de resíduo quadrático módulo m.
O que residualidade quadrática significa para módulos gerais
Na teoria elementar dos números um resíduo quadrático módulo um primo p costuma significar um inteiro a não divisível por p para o qual a congruência x ao quadrado igual a a módulo p tem solução; zero costuma ser tratado à parte como o quadrado trivial. Para um módulo composto m a mesma definição se estende de forma limpa: a é resíduo quadrático módulo m quando existe pelo menos um inteiro x com x ao quadrado congruente a a módulo m, incluindo o caso a congruente a zero.
As soluções vêm em padrões que dependem da fatoração em potências primas de m; por exemplo módulo um primo há zero ou duas raízes não nulas para cada classe de resíduo não nula que é um quadrado, enquanto módulos compostos podem admitir mais raízes. Ferramentas clássicas como os símbolos de Legendre e Jacobi dão testes rápidos quando m é um primo ímpar ou quando você só precisa de um caráter multiplicativo, mas não listam por si só cada raiz para m arbitrário.
Uma varredura direta de x de zero até m menos um avalia cada classe de quadrado exatamente uma vez e portanto responde tanto à existência quanto à enumeração para qualquer módulo dentro de um limite de tamanho fixo.
Onde checagens de quadrados modulares aparecem no trabalho real
Programadores de competição muitas vezes precisam de um oráculo rápido antes de invocar Tonelli–Shanks ou uma combinação CRT de raízes em potências primas: se o bit de resíduo for falso, não vale construir uma raiz quadrada. Estudantes de criptografia verificam exemplos de cifras no estilo Rabin, exercícios de reciprocidade quadrática e variantes toy de Diffie–Hellman que mencionam símbolos de resíduo. Engenheiros reconciliando agendas periódicas ou experimentos de buckets de hash às vezes perguntam se um passo é uma classe de quadrado módulo um período composto.
Se você só precisa de um sim ou não no estilo do símbolo de Legendre para um primo grande além do limite de varredura, fatore ou reduza primeiro; dentro do teto esta página é a resposta construtiva completa.
Casos de uso
Checagens de lição e competição
Decida se a é um quadrado módulo m e leia cada raiz em 0..m-1 para exercícios de teoria dos números sem montar um solucionador CRT completo.
Pré-filtro antes da extração de raízes
Rejeite não resíduos cedo em um pipeline que de outro modo tentaria algoritmos de raiz quadrada modular em módulos compostos ou primos.
Perguntas frequentes
O que é um resíduo quadrático módulo m?
Um inteiro a é resíduo quadrático módulo m se existe um inteiro x tal que x² ≡ a (mod m). Esta ferramenta relata esse fato e lista cada tal x em 0..m-1.
Por que m deve ser pelo menos 2?
O módulo 0 é indefinido para congruências nesta superfície de produto, e o módulo 1 colapsa todo inteiro a uma única classe.
Qual tamanho de módulo é suportado?
m deve ser um inteiro de 2 a 1,000,000 inclusive. O candidato a pode ser qualquer inteiro seguro; é reduzido módulo m antes da varredura.
Quanto custa?
A ferramenta do navegador é grátis e roda localmente.
3 é um resíduo quadrático módulo 7?
Não. Elevando ao quadrado cada resto módulo 7, só aparecem 0, 1, 2 ou 4, então nenhum inteiro ao quadrado deixa 3, e a lista de raízes vem vazia.
Ferramentas relacionadas
Para desenvolvedores — acesso via API
Tudo nesta página está disponível via API. Esta seção é para equipes que querem integrar a ferramenta aos próprios sistemas; quem não precisa disso pode simplesmente usar a ferramenta acima.
Endpoint
Autenticação por token Bearer. Um único POST coloca a tarefa na fila; o resultado chega por webhook ou link assinado.
Chame do seu código
curl -X POST https://api.kit.forhosting.com/numth/quadratic-residue \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":2,"m":7}'const res = await fetch("https://api.kit.forhosting.com/numth/quadratic-residue", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": 2,
"m": 7
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/quadratic-residue",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": 2,
"m": 7
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/quadratic-residue", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":2,"m":7}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":2,"m":7}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/quadratic-residue", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Exemplo de requisição
{
"a": 2,
"m": 7
}Exemplo de resposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.quadratic_residue",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}A API é assíncrona: cada chamada devolve um task_id na hora. Se preferir polling, consulte o status a até 1 requisição por segundo.
Preço
Preço publicado, sem tokens nem créditos escondidos. Tarefa que falha não é cobrada.
Limites
min_m | 2 |
max_m | 1000000 |
max_abs_a | 9007199254740991 |
Erros
| HTTP | Código | O que significa |
|---|---|---|
401 | unauthorized | Token ausente ou inválido. Confira o header Authorization. |
402 | insufficient_balance | Saldo insuficiente para esta tarefa. Faça uma recarga e tente de novo. |
404 | unknown_type | Esse tipo de tarefa não existe. Confira o campo type no catálogo. |
429 | rate_limited | Muitas requisições em pouco tempo. Espere um instante e tente de novo. |
Notas técnicas
O que residualidade quadrática significa para módulos gerais
Essa abordagem exaustiva é o que este endpoint implementa: apenas aritmética inteira determinística, sem arredondamento em ponto flutuante, e um formato JSON estável que você pode afirmar em testes.
Contrato de entrada, limites e campos da resposta
Envie inteiros a e m. Checagens típicas de sala: dois é resíduo quadrático módulo sete porque três ao quadrado é nove que é dois mod sete, e as raízes são três e quatro; três não é resíduo quadrático módulo sete. Não inteiros, campos obrigatórios vazios e módulos acima do teto falham a validação com mensagem clara que nomeia o campo. O módulo m deve ser pelo menos dois e no máximo um milhão; valores abaixo de dois são rejeitados com invalid_input e não são cobrados, porque aritmética modular com módulo zero ou um não é superfície de produto suportada. O candidato a pode ser negativo ou maior que m; ele é reduzido a a_mod no intervalo semiaberto de zero inclusivo a m exclusivo antes da busca de quadrados. O booleano opcional list_residues (aliases list_all e all_residues) pede cada valor distinto de x ao quadrado módulo m, ordenado de forma crescente, junto com residue_count. Em sucesso o payload sempre inclui a, m, a_mod, is_quadratic_residue, roots como a lista completa de soluções em zero até m menos um, e root_count. Quando list_residues é verdadeiro para m igual a sete você obtém as classes ordenadas zero, um, dois e quatro — a imagem do mapa de elevação ao quadrado no anel de inteiros módulo sete.
Onde checagens de quadrados modulares aparecem no trabalho real
Professores atribuem problemas como listar todos os resíduos quadráticos módulo vinte e um ou decidir se cinco é um quadrado módulo treze e querem uma resposta JSON determinística em vez de uma tabela à mão que pode conter erros de um. Como a capacidade é um motor de parse puro não há deriva de modelo, nem chave API externa, nem estado armazenado: o mesmo par sempre produz as mesmas raízes e a mesma lista opcional de resíduos. O preço da API é a base publicada de US$ 0,002 por item bem-sucedido; validação falha não consome saldo.
Casos de integração
Enumerar classes de resíduo
Defina list_residues como verdadeiro para obter a imagem ordenada do mapa de elevação ao quadrado módulo m para tabelas, slides didáticos ou testes baseados em propriedades.
Perguntas técnicas
0 é considerado resíduo quadrático?
Sim. 0² ≡ 0 (mod m), então a_mod = 0 é sempre um resíduo e inclui a raiz 0 (e possivelmente outras para m composto).