Calculadora dos Símbolos de Legendre e Jacobi
Use esta calculadora de símbolos de Legendre e Jacobi para informar valores, ajustar opções e analisar resultados em uma área de trabalho compacta e responsiva.
Os resultados são calculados automaticamente conforme você informa os dados.
Resultado
▼ Veja explicações e dicas abaixo ▼
Calculadoras relacionadas
O que são resíduos quadráticos?
Um resíduo quadrático é um número que pode ser obtido elevando outro número ao quadrado na aritmética modular. Na aritmética comum, \(4\) é um quadrado porque \(2^2 = 4\). Na aritmética modular, um número \(r\) é um resíduo quadrático módulo \(n\) quando existe algum inteiro \(x\) tal que
$$
x^2 \equiv r \pmod{n}
$$
Isso significa que \(x^2\) e \(r\) deixam o mesmo resto após a divisão por \(n\).
Por exemplo, módulo \(13\),
$$
6^2 = 36 \equiv 10 \pmod{13}
$$
portanto \(10\) é um resíduo quadrático módulo \(13\). Por outro lado, \(5\) não é um quadrado módulo \(13\), portanto é um não resíduo quadrático módulo \(13\).
Os símbolos de Legendre e de Jacobi são formas compactas de perguntar se um número se comporta como um quadrado módulo um inteiro ímpar. O símbolo de Legendre é usado quando o módulo é um primo ímpar. O símbolo de Jacobi estende uma notação semelhante a módulos compostos ímpares, mas sua interpretação é mais sutil.
A notação parece uma fração, como \(\left(\frac{a}{n}\right)\), mas não representa uma divisão. É um símbolo cujo valor é sempre um destes três inteiros:
$$
-1,\quad 0,\quad 1
$$
Por que esses símbolos são importantes
Os resíduos quadráticos aparecem em toda a teoria elementar dos números, na aritmética modular e na matemática relacionada à criptografia. Eles ajudam a responder perguntas como:
- Uma congruência da forma \(x^2 \equiv a \pmod{n}\) é possível?
- Um número pode ser classificado como quadrado ou não quadrado módulo um primo ímpar?
- Como a reciprocidade quadrática pode transformar uma pergunta aparentemente difícil sobre resíduos em uma pergunta mais simples?
- Por que um módulo composto se comporta de modo diferente de um módulo primo?
Para estudantes, os símbolos de Legendre e de Jacobi são uma ponte entre a aritmética modular básica e ferramentas mais avançadas, como o critério de Euler e a reciprocidade quadrática. Para quem estuda temas relacionados à criptografia, eles também são uma base útil para raízes quadradas modulares, conceitos de testes de primalidade e residuidade quadrática.
Termos essenciais
- Módulo: O número \(n\) usado na aritmética modular. Trabalhar módulo \(n\) significa comparar os restos após a divisão por \(n\).
- Classe de resíduos: A forma do resto de um número módulo \(n\). Por exemplo, \(-3 \equiv 10 \pmod{13}\), portanto \(-3\) e \(10\) estão na mesma classe de resíduos módulo \(13\).
- Resíduo quadrático: Uma classe de resíduos que é igual a \(x^2 \pmod{n}\) para algum inteiro \(x\).
- Não resíduo quadrático: Uma classe de resíduos que não é um quadrado módulo \(n\), geralmente considerada entre os valores coprimos com o módulo.
- Máximo divisor comum: \(\gcd(a,n)\) é o maior inteiro positivo que divide tanto \(a\) quanto \(n\).
- Símbolo de Legendre: O símbolo \(\left(\frac{a}{p}\right)\) para um módulo primo ímpar \(p\).
- Símbolo de Jacobi: O símbolo \(\left(\frac{a}{n}\right)\) para um módulo positivo ímpar \(n\), em que \(n\) pode ser composto.
- Reciprocidade quadrática: Um teorema que relaciona \(\left(\frac{p}{q}\right)\) a \(\left(\frac{q}{p}\right)\) para primos ímpares e possui uma forma correspondente para o símbolo de Jacobi para inteiros ímpares.
- Critério de Euler: Um teste para módulos primos que relaciona o símbolo de Legendre à exponenciação modular.
Como funciona o símbolo de Legendre
Para um primo ímpar \(p\) e um inteiro \(a\), o símbolo de Legendre é definido por
$$
\left(\frac{a}{p}\right)=
\begin{cases}
0, & \text{if } p \mid a,\\
1, & \text{if } a \text{ is a nonzero quadratic residue modulo } p,\\
-1, & \text{if } a \text{ is a quadratic non-residue modulo } p.
\end{cases}
$$
Como o módulo é primo, a interpretação é direta:
- \(\left(\frac{a}{p}\right)=1\) significa que \(x^2 \equiv a \pmod{p}\) tem solução e \(a\) não é divisível por \(p\).
- \(\left(\frac{a}{p}\right)=-1\) significa que \(x^2 \equiv a \pmod{p}\) não tem solução.
- \(\left(\frac{a}{p}\right)=0\) significa que \(a\) é divisível por \(p\).
O valor depende apenas da classe de resíduos de \(a\) módulo \(p\). Por exemplo, como \(-3 \equiv 10 \pmod{13}\), os símbolos \(\left(\frac{-3}{13}\right)\) e \(\left(\frac{10}{13}\right)\) têm o mesmo valor.
O critério de Euler fornece uma verificação útil para módulos primos. Se \(p\) é um primo ímpar e \(p \nmid a\), então
$$
a^{\frac{p-1}{2}} \equiv \left(\frac{a}{p}\right) \pmod{p}
$$
Quando o símbolo de Legendre é \(-1\), o resultado da exponenciação modular aparece como \(p-1\) módulo \(p\), porque \(-1 \equiv p-1 \pmod{p}\).
Como funciona o símbolo de Jacobi
O símbolo de Jacobi usa a mesma notação, mas permite um módulo composto positivo ímpar. Se
$$
n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}
$$
é a fatoração em primos do \(n\) ímpar, então o símbolo de Jacobi é definido como
$$
\left(\frac{a}{n}\right)=
\left(\frac{a}{p_1}\right)^{e_1}
\left(\frac{a}{p_2}\right)^{e_2}
\cdots
\left(\frac{a}{p_k}\right)^{e_k}
$$
Cada fator à direita é um símbolo de Legendre. Essa definição explica por que o símbolo de Jacobi coincide com o símbolo de Legendre quando \(n\) é primo.
A diferença importante está na interpretação. Para \(n\) composto:
- \(\left(\frac{a}{n}\right)=-1\) exclui \(a\) como resíduo quadrático módulo \(n\).
- \(\left(\frac{a}{n}\right)=0\) significa que \(a\) e \(n\) têm um fator em comum.
- \(\left(\frac{a}{n}\right)=1\) significa que \(a\) passa em um teste necessário, mas isso não garante que \(a\) seja de fato um quadrado módulo \(n\).
Esse último ponto é um dos erros mais comuns. Um valor de Jacobi igual a \(1\) não equivale a dizer que “existe uma raiz quadrada” quando o módulo é composto.
Como a reciprocidade quadrática ajuda a calcular o símbolo
A reciprocidade quadrática fornece regras para transformar um símbolo em outro, geralmente com números menores. Para valores positivos ímpares coprimos \(m\) e \(n\), a regra de reciprocidade do símbolo de Jacobi pode ser escrita como
$$
\left(\frac{m}{n}\right)
=
(-1)^{\frac{(m-1)(n-1)}{4}}
\left(\frac{n}{m}\right)
$$
Essa fórmula significa que trocar o numerador e o denominador do símbolo pode ou não mudar o sinal. O sinal muda exatamente quando os dois valores ímpares são congruentes a \(3 \pmod{4}\).
A regra do fator \(2\) também é essencial:
$$
\left(\frac{2}{n}\right)
=
(-1)^{\frac{n^2-1}{8}}
$$
De forma equivalente, para \(n\) ímpar:
$$
\left(\frac{2}{n}\right)=
\begin{cases}
1, & \text{if } n \equiv 1 \text{ or } 7 \pmod{8},\\
-1, & \text{if } n \equiv 3 \text{ or } 5 \pmod{8}.
\end{cases}
$$
Um cálculo baseado na reciprocidade geralmente segue este padrão:
- Reduza o valor do numerador \(a\) módulo o módulo ímpar \(n\).
- Se o valor reduzido tiver um fator em comum com \(n\), o símbolo será \(0\).
- Remova fatores de \(2\) do numerador e aplique a regra de sinal do fator \(2\).
- Troque o numerador e o denominador usando a reciprocidade quadrática.
- Reduza novamente e repita até que o denominador chegue a \(1\) ou até que um fator comum force o valor a ser \(0\).
Por isso, o cálculo costuma se parecer com o algoritmo de Euclides: ele reduz repetidamente os números enquanto acompanha possíveis mudanças de sinal.
Exemplos práticos dos símbolos de Legendre e de Jacobi
Exemplo 1: um resíduo quadrático módulo um primo
Considere \(a=10\) e \(p=13\). Para verificar se \(10\) é um quadrado módulo \(13\), eleve pequenos valores ao quadrado:
$$
1^2 \equiv 1 \pmod{13}
$$
$$
2^2 \equiv 4 \pmod{13}
$$
$$
3^2 \equiv 9 \pmod{13}
$$
$$
4^2 \equiv 3 \pmod{13}
$$
$$
5^2 \equiv 12 \pmod{13}
$$
$$
6^2 \equiv 10 \pmod{13}
$$
Como \(6^2 \equiv 10 \pmod{13}\), \(10\) é um resíduo quadrático módulo \(13\):
$$
\left(\frac{10}{13}\right)=1
$$
Exemplo 2: um não resíduo quadrático módulo um primo
Usando o mesmo módulo primo \(13\), os resíduos quadráticos não nulos são
$$
\{1,3,4,9,10,12\}
$$
O valor \(5\) não está nesse conjunto, portanto \(5\) é um não resíduo quadrático módulo \(13\):
$$
\left(\frac{5}{13}\right)=-1
$$
O critério de Euler leva à mesma conclusão porque
$$
5^{\frac{13-1}{2}}=5^6 \equiv -1 \pmod{13}
$$
Uma calculadora que apresente a verificação de Euler como um resíduo não negativo mostraria isto como
$$
12 \pmod{13}
$$
porque \(12 \equiv -1 \pmod{13}\).
Exemplo 3: um valor negativo no numerador
Os valores negativos são interpretados por meio de sua classe de resíduos. Para \(a=-3\) e \(n=13\),
$$
-3 \equiv 10 \pmod{13}
$$
Portanto,
$$
\left(\frac{-3}{13}\right)=
\left(\frac{10}{13}\right)=1
$$
O sinal do valor informado originalmente é menos importante que seu valor reduzido módulo \(n\).
Exemplo 4: um valor de Jacobi igual a 1 que não é um quadrado
Agora use o módulo composto \(15\):
$$
15=3\cdot 5
$$
O símbolo de Jacobi se fatoriza como
$$
\left(\frac{2}{15}\right)
=
\left(\frac{2}{3}\right)
\left(\frac{2}{5}\right)
$$
Como \(2\) é um não resíduo módulo \(3\) e também um não resíduo módulo \(5\),
$$
\left(\frac{2}{15}\right)=(-1)(-1)=1
$$
No entanto, os resíduos quadráticos reais módulo \(15\) são
$$
\{x^2 \bmod 15 : x=0,1,\ldots,14\}=\{0,1,4,6,9,10\}
$$
O valor \(2\) não está nesse conjunto. Portanto, embora
$$
\left(\frac{2}{15}\right)=1
$$
não exista solução para
$$
x^2 \equiv 2 \pmod{15}
$$
Este exemplo mostra por que um valor de Jacobi igual a \(1\) é apenas uma condição necessária para módulos compostos.
Como interpretar o resultado
O significado do resultado depende de o cálculo ser de Legendre ou de Jacobi.
| Valor do símbolo | Modo Legendre com módulo primo ímpar | Modo Jacobi com módulo composto ímpar |
|---|---|---|
| \(1\) | \(a \bmod n\) é um resíduo quadrático não nulo. | Uma raiz quadrada é possível, mas não garantida. Consulte a lista de resíduos reais quando disponível. |
| \(0\) | \(a\) é divisível pelo módulo primo. | \(a\) e \(n\) têm um fator em comum, portanto o símbolo não está classificando um resíduo coprimo. |
| \(-1\) | \(a \bmod n\) é um não resíduo quadrático. | \(a \bmod n\) não é um resíduo quadrático módulo \(n\). |
O valor reduzido \(a \bmod n\) é o que importa para o teste de resíduos. Se o valor informado originalmente for negativo ou maior que o módulo, o resultado deve ser interpretado usando a classe de resíduos reduzida.
O valor \(\gcd(a,n)\) também é importante. Um máximo divisor comum não trivial significa que o símbolo é \(0\). Nesse caso, o resultado informa sobre um fator compartilhado, não sobre uma classificação simples entre resíduo e não resíduo entre as unidades módulo \(n\).
Quando o módulo é pequeno o suficiente para a tabela de resíduos, ela fornece evidência direta: lista valores de \(x^2 \bmod n\). Se \(a \bmod n\) aparecer nessa lista, é um resíduo quadrático real para esse módulo. Se não aparecer, não existe raiz quadrada para essa classe de resíduos.
No modo Legendre, a verificação de Euler é uma conferência que usa exponenciação modular:
$$
a^{\frac{n-1}{2}} \bmod n
$$
Ela é exibida apenas para módulos primos. Não é usada como interpretação do símbolo de Jacobi para módulos compostos.
Erros e equívocos comuns
Erro 1: tratar o símbolo como uma fração.
A notação \(\left(\frac{a}{n}\right)\) não representa uma divisão. É um símbolo da teoria dos números com valor \(-1\), \(0\) ou \(1\).
Erro 2: usar o modo Legendre com um módulo composto.
O símbolo de Legendre requer um módulo primo ímpar. Se o módulo for ímpar, mas composto, use o modo Jacobi ou o modo Automático.
Erro 3: supor que o valor de Jacobi \(1\) prova a existência de uma raiz quadrada.
Para \(n\) composto, \(\left(\frac{a}{n}\right)=1\) não garante que \(x^2 \equiv a \pmod{n}\) tenha solução.
Erro 4: esquecer de reduzir \(a\) módulo \(n\).
Valores como \(-3\), \(10\) e \(23\) podem representar a mesma classe de resíduos módulo \(13\). O que importa é o valor reduzido.
Erro 5: confundir o símbolo com uma raiz quadrada.
O valor do símbolo informa se um resíduo é um quadrado, não é um quadrado ou compartilha um fator no sentido relevante. Ele não constrói um valor de \(x\) tal que \(x^2 \equiv a \pmod{n}\).
Erro 6: esperar a roda de resíduos para todo módulo.
O símbolo ainda pode ser calculado para módulos suportados maiores, mas a visualização e a tabela de resíduos só são geradas quando o módulo é menor ou igual ao limite escolhido para a lista de resíduos.
Quando usar os símbolos de Legendre e de Jacobi
Use estes símbolos quando quiser:
- classificar se um inteiro é um resíduo quadrático módulo um primo ímpar;
- estudar ou praticar a reciprocidade quadrática;
- comparar um teste simbólico de resíduos com resíduos quadráticos reais para módulos pequenos;
- entender por que módulos primos e compostos se comportam de maneira diferente;
- testar uma condição necessária para a residuidade quadrática módulo um inteiro composto ímpar;
- desenvolver a intuição sobre temas de aritmética modular presentes em cursos de teoria elementar dos números e assuntos relacionados à criptografia.
Limitações e pontos importantes
Os símbolos de Legendre e de Jacobi são poderosos, mas não respondem a todas as perguntas de aritmética modular.
O símbolo de Legendre se aplica a módulos primos ímpares. O símbolo de Jacobi se aplica a módulos positivos ímpares, incluindo módulos compostos ímpares, mas seu valor deve ser interpretado com cuidado. Em particular, um valor de Jacobi igual a \(1\) não prova que existe uma raiz quadrada modular.
A calculadora aceita \(a\) como um inteiro simples, opcionalmente precedido por um sinal de menos, com até 256 algarismos decimais. Ela não aceita números decimais, frações, valores infinitos ou notação científica. O módulo deve ser ímpar e satisfazer
$$
3 \le n \le 1{,}000{,}000{,}000
$$
O limite da lista de resíduos deve ser um inteiro de \(9\) a \(101\). Se \(n\) for maior que o limite selecionado, o símbolo ainda será calculado, mas a roda e a tabela de resíduos serão omitidas.
Digite \(a\) como um inteiro simples, opcionalmente precedido por um sinal de menos, com até 256 algarismos, e \(n\) como algarismos decimais simples de \(3\) a \(1{,}000{,}000{,}000\). O algoritmo do símbolo e a verificação de Euler usam aritmética inteira exata; notação científica e valores decimais não são aceitos.
A calculadora avalia um par \((a,n)\) por vez. Ela não processa muitos símbolos em lote e não calcula raízes quadradas modulares. Se você precisar de uma solução real para
$$
x^2 \equiv a \pmod{n}
$$
você precisará de um método de raiz quadrada modular, não apenas de um símbolo de Legendre ou de Jacobi.
A detecção de primo ou composto é usada para escolher o modo apropriado no modo Automático e para impor as condições do modo Legendre. Ela não deve ser considerada substituta de um processo especializado de teste de primalidade em contextos exigentes de criptografia ou pesquisa.
Como usar esta calculadora
- Digite o inteiro do numerador \(a\).
- Digite um módulo ímpar \(n\) de \(3\) a \(1{,}000{,}000{,}000\).
- Escolha o modo Automático, Legendre ou Jacobi. O modo Automático usa Legendre para \(n\) primo ímpar e Jacobi para \(n\) composto ímpar.
- Defina o limite da lista de resíduos de \(9\) a \(101\). Isso controla quando a roda de resíduos e a tabela de resíduos quadráticos reais serão exibidas.
- Leia o valor principal do símbolo, o tipo de cálculo, \(a \bmod n\), \(\gcd(a,n)\), o tipo de módulo e a verificação de Euler, se ela for exibida.
- Para módulos pequenos, compare o valor do símbolo com a roda e a tabela de resíduos.
- Consulte o desenvolvimento passo a passo para ver as reduções, as regras do fator \(2\), as trocas de reciprocidade e as mudanças de sinal.
- Use os botões de exemplo para carregar um exemplo de resíduo, um exemplo de não resíduo ou um exemplo de Jacobi.
Perguntas frequentes
O símbolo de Jacobi é igual ao símbolo de Legendre?
Eles coincidem quando o valor do denominador é um primo ímpar. O símbolo de Legendre é definido para um módulo primo ímpar, enquanto o símbolo de Jacobi é definido para módulos positivos ímpares que podem ser compostos. Portanto, a mesma notação pode ter um nível de interpretação diferente dependendo de o módulo ser primo ou composto.
O que significa um valor do símbolo igual a 0?
Um valor de \(0\) significa que o numerador e o módulo não são coprimos. Na prática, o valor reduzido \(a\) tem um fator em comum com \(n\). No modo Legendre, isso acontece exatamente quando o módulo primo divide \(a\).
Por que um valor de Jacobi igual a 1 não garante uma raiz quadrada?
Para \(n\) composto, o símbolo de Jacobi multiplica as informações dos símbolos de Legendre correspondentes aos fatores primos de \(n\). Dois fatores que são não resíduos podem resultar em um valor de Jacobi igual a \(1\), mesmo quando o número original não é um quadrado módulo o módulo composto. Por isso, \(\left(\frac{2}{15}\right)=1\), embora \(2\) não seja um quadrado módulo \(15\).
Por que o módulo deve ser ímpar?
O símbolo de Legendre padrão usa um módulo primo ímpar, e o símbolo de Jacobi padrão usa um módulo positivo ímpar. Módulos pares exigem convenções e símbolos relacionados diferentes, portanto estão fora do escopo desta calculadora.
A calculadora encontra raízes quadradas modulares?
Não. Ela calcula o símbolo de Legendre ou de Jacobi e, para módulos pequenos, lista os resíduos quadráticos reais. Encontrar um valor de \(x\) tal que \(x^2 \equiv a \pmod{n}\) é um problema separado de raiz quadrada modular.
Fontes e referências
Livros
- Victor Shoup. A Computational Introduction to Number Theory and Algebra. 2ª ed., Cambridge University Press, 2009. Capítulo 12, especialmente §§12.1–12.3 sobre o símbolo de Legendre, o símbolo de Jacobi e o cálculo do símbolo de Jacobi. Versão oficial do autor, 2.1: https://www.shoup.net/ntb/ntb-v2_1.pdf. Informações editoriais: https://assets.cambridge.org/97805215/16440/frontmatter/9780521516440_frontmatter.pdf.
- William Stein. Elementary Number Theory: Primes, Congruences, and Secrets: A Computational Approach. Springer New York, 2009. Capítulo 4, especialmente §4.1 sobre resíduos quadráticos e o símbolo de Legendre, §4.2 sobre o critério de Euler e o Exercício 4.9 sobre o símbolo de Jacobi. Página oficial do livro e PDF gratuito legal: https://wstein.org/ent/. Página da Springer: https://link.springer.com/book/10.1007/b13279.
Fontes on-line e educacionais
- MIT OpenCourseWare. “Quadratic Residues, Quadratic Reciprocity, Lecture 9 Notes.” 18.781 Theory of Numbers, primavera de 2012, acessado em 29 de junho de 2026. https://ocw.mit.edu/courses/18-781-theory-of-numbers-spring-2012/resources/mit18781s12lec9/.
- Eric W. Weisstein. “Legendre Symbol.” MathWorld—A Wolfram Resource, acessado em 29 de junho de 2026. https://mathworld.wolfram.com/LegendreSymbol.html.
- Eric W. Weisstein. “Jacobi Symbol.” MathWorld—A Wolfram Resource, acessado em 29 de junho de 2026. https://mathworld.wolfram.com/JacobiSymbol.html.
- Eric W. Weisstein. “Euler's Criterion.” MathWorld—A Wolfram Resource, acessado em 29 de junho de 2026. https://mathworld.wolfram.com/EulersCriterion.html.