Resíduo quadrático

Na teoria dos números, um inteiro $q$ é chamado de resíduo quadrático módulo $n$ se for congruente a um quadrado perfeito módulo $n$; ou seja, se existe um inteiro $x$ tal que:

$x^{2}\equiv q{\pmod {n}}.$

Caso contrário, $q$ é chamado de não-resíduo quadrático módulo $n$.

Originalmente um conceito matemático abstrato do ramo da teoria dos números conhecido como aritmética modular, os resíduos quadráticos são agora usados em aplicações que vão desde a engenharia acústica até a criptografia e a fatoração de grandes números.

História, convenções e fatos elementares

Fermat, Euler, Lagrange, Legendre e outros teóricos dos números dos séculos XVII e XVIII estabeleceram teoremas e formaram conjecturas sobre resíduos quadráticos, mas o primeiro tratamento sistemático é o § IV da Disquisitiones Arithmeticae de Gauss (1801). O Artigo 95 introduz a terminologia "resíduo quadrático" e "não-resíduo quadrático", e afirma que, se o contexto deixar claro, o adjetivo "quadrático" pode ser eliminado.

Para uma determinada lista de resíduos quadráticos, o módulo $n$ pode ser obtido simplesmente elevando ao quadrado os números $0,1,...,n-1$. Porque $a^{2}\equiv (n-a)^{2}{\pmod {n}}$, a lista de quadrados módulo $n$ é simétrica em torno de ${\frac {n}{2}}$, e a lista só precisa ir até tal valor. Isso pode ser visto na tabela abaixo.

Assim, o número de resíduos quadráticos módulo $n$ não pode exceder ${\frac {n}{2}}+1$ ($n$ par) ou ${\frac {n+1}{2}}$ ($n$ ímpar).

O produto de dois resíduos é sempre um resíduo.

Módulo primo

Módulo 2, todo inteiro é um resíduo quadrático.

Módulo um número primo ímpar $p$ onde há ${\frac {p+1}{2}}$ resíduos (incluindo $0$) e ${\frac {p-1}{2}}$ não-resíduos, pelo critério de Euler. Nesse caso, costuma-se considerar 0 como um caso especial e trabalhar dentro do grupo multiplicativo de elementos não nulos do campo $\mathbb {Z} /p\mathbb {Z}$. (Em outras palavras, toda classe de congruência, exceto o zero módulo $p$, tem um inverso multiplicativo. Isso não é verdade para os módulos compostos.)

Seguindo esta convenção, o inverso multiplicativo de um resíduo é um resíduo, e o inverso de um não-resíduo é um não-resíduo.

Seguindo esta convenção, módulo um número primo ímpar, há um número igual de resíduos e não-resíduos.

Módulo um primo, o produto de dois não-resíduos é um resíduo e o produto de um não-resíduo e um resíduo (diferente de zero) é um não-resíduo.

O primeiro suplemento à lei da reciprocidade quadrática é que se $p\equiv 1{\pmod {4}}$ então $-1$ é um resíduo quadrático módulo $p$, e se $p\equiv 3{\pmod {4}}$ então $-1$ é um não-resíduo quadrático módulo $p$. Isso implica o seguinte:

Se $p\equiv 1{\pmod {4}}$, o negativo de um resíduo módulo $p$ é um resíduo e o negativo de um não-resíduo é um não-resíduo.

Se $p\equiv 3{\pmod {4}}$, o negativo de um resíduo módulo $p$ é um não-resíduo e o negativo de um não-resíduo é um resíduo.

Módulo potência de primo

Todos os quadrados ímpares são $\equiv 1{\pmod {8}}$ e, portanto, também $\equiv 1{\pmod {4}}$. Se $a$ é um número ímpar e $m=8$, $16$ ou alguma potência superior de $2$, então $a$ é um resíduo módulo $m$ se e somente se $a\equiv 1{\pmod {8}}$.

Por exemplo, $({\text{mod}}\ {32})$ os quadrados ímpares são

$1^{2}\equiv 15^{2}\equiv 1$

$3^{2}\equiv 13^{2}\equiv 9$

$5^{2}\equiv 11^{2}\equiv 25$

$7^{2}\equiv 9^{2}\equiv 49\equiv 17$

e os pares são

$0^{2}\equiv 8^{2}\equiv 16^{2}\equiv 0$

$2^{2}\equiv 6^{2}\equiv 10^{2}\equiv 14^{2}\equiv 4$

$4^{2}\equiv 12^{2}\equiv 16$.

Portanto, um número diferente de zero é um resíduo ${\bmod {8}}$, $16$, etc., se e somente se for da forma $4^{k}(8n+1)$.

Um número $a$ relativamente primo a um primo ímpar $p$ é um resíduo módulo qualquer potência de $p$ se e somente se for um resíduo módulo $p$.

Se o módulo for $p^{n}$,

então $p^{k}a$

é um resíduo módulo $p^{n}$ se $k\geq n$

é um não-resíduo módulo $p^{n}$ se $k<n$ for ímpar

é um resíduo módulo $p^{n}$ se $k<n$ é par e $a$ é um resíduo

é um não-resíduo módulo $p^{n}$ se $k<n$ for par e $a$ for um não-resíduo.

Observe que as regras são diferentes para potências de dois e potências de primos ímpares.

Módulo uma potência prima ímpar $n=p^{k}$, os produtos de resíduos e não-resíduos relativamente primos a $p$ obedecem às mesmas regras que o ${\bmod {p}}$; $p$ é um não-resíduo, e em geral todos os resíduos e não-resíduos obedecem às mesmas regras, exceto que os produtos serão zero se a potência de $p$ no produto $\geq n$.

Módulo 8, o produto dos não-resíduos 3 e 5 é o não-resíduo 7, e da mesma forma para as permutações de 3, 5 e 7. Na verdade, o grupo multiplicativo dos não-resíduos e 1 forma o Klein 4.

Módulo composto que não é potência de primo

O fato básico neste caso é

se $a$ é um resíduo módulo $n$, então $a$ é um resíduo módulo $p^{k}$ para toda potência prima dividindo $n$.

se $a$ é um não-resíduo módulo $n$, então $a$ é um não-resíduo módulo $p^{k}$ para pelo menos uma potência prima dividindo $n$.

Módulo um número composto, o produto de dois resíduos é um resíduo. O produto de um resíduo e um não-resíduo pode ser um resíduo, um não-resíduo ou zero.

Por exemplo, da tabela para módulo 6: ${\boldsymbol {1}},2,{\boldsymbol {3}},{\boldsymbol {4}},5$ (resíduos em negrito). O produto do resíduo 3 e do não-resíduo 5 é o resíduo 3, enquanto o produto do resíduo 4 e do não-resíduo 2 é o não-resíduo 2.

Além disso, o produto de dois não-resíduos pode ser um resíduo, um não-resíduo ou zero.

Por exemplo, da tabela para o módulo 15: ${\boldsymbol {1}},2,3,{\boldsymbol {4}},5,{\boldsymbol {6}},7,8,{\boldsymbol {9}},{\boldsymbol {10}},11,12,13,14$ (resíduos em negrito). O produto dos não-resíduos 2 e 8 é o resíduo 1, enquanto o produto dos não-resíduos 2 e 7 é o não-resíduo 14.

Este fenômeno pode ser melhor descrito usando o vocabulário da álgebra abstrata. As classes de congruência relativamente primas ao módulo são um grupo em multiplicação, denominado grupo de unidades do anel ${\boldsymbol {\mathrm {Z} }}/n{\boldsymbol {\mathrm {Z} }}$, e os quadrados são um subgrupo dele. Diferentes não-resíduos podem pertencer a diferentes coclasses, e não existe uma regra simples que preveja em qual delas seu produto estará. Módulo um primo, há apenas o subgrupo de quadrados e uma única coclasse.

O fato de que, por exemplo, módulo 15 o produto dos não-resíduos 3 e 5, ou do não-resíduo 5 e o resíduo 9, ou os dois resíduos 9 e 10 são todos zero vem de trabalhar no anel completo ${\boldsymbol {\mathrm {Z} }}/n{\boldsymbol {\mathrm {Z} }}$, que tem divisores de zero para composto $n$.

Por esta razão alguns autores acrescentam à definição que um resíduo quadrático $a$ deve não apenas ser um quadrado, mas também deve ser relativamente primo ao módulo $n$. ($a$ é coprimo a $n$ se e somente se $a^{2}$ for coprimo a $n$.)

Embora torne as coisas mais organizadas, este artigo não insiste que os resíduos devem ser coprimos ao módulo.

Notações

Gauss usou $\mathrm {R}$ e $\mathrm {N}$ para denotar residuosidade e não-residuosidade, respectivamente;

por exemplo, $2\ \mathrm {R} \ 7$ e $5\ \mathrm {N} \ 7$, ou $1\ \mathrm {R} \ 8$ e $3\ \mathrm {N} \ 8$.

Embora esta notação seja compacta e conveniente para alguns propósitos, uma notação mais útil é o símbolo de Legendre, também chamado de caráter quadrático, que é definido para todos os inteiros $a$ e números primos ímpares positivos $p$ como

$\left({\frac {a}{p}}\right)={\begin{cases}\;\;\,0&{\text{ se }}p{\text{ divide }}a\\+1&{\text{ se }}a\operatorname {R} p{\text{ e }}p{\text{ não divide }}a\\-1&{\text{ se }}a\operatorname {N} p{\text{ e }}p{\text{ não divide }}a\end{cases}}$

Existem duas razões pelas quais os números $\equiv 0{\pmod {p}}$ são tratados de maneira especial. Como vimos, isso torna muitas fórmulas e teoremas mais fáceis de definir. A outra razão (relacionada) é que o caractere quadrático é um homomorfismo do grupo multiplicativo de classes de congruência diferente de zero módulo $p$ para os números complexos sob multiplicação. Configurando $({\tfrac {np}{p}})=0$ permite que seu domínio seja estendido ao semigrupo multiplicativo de todos os inteiros.

Uma vantagem desta notação sobre a de Gauss é que o símbolo de Legendre é uma função que pode ser usada em fórmulas. Também pode ser facilmente generalizado para resíduos cúbicos, quárticos e de maior potência.

Há uma generalização do símbolo de Legendre para valores compostos de $p$, o símbolo de Jacobi, mas suas propriedades não são tão simples: se $m$ é composto e o símbolo de Jacobi $({\tfrac {a}{m}})=-1,$ então $a\ \mathrm {N} \ m$, e se $a\ \mathrm {R} \ m$ então $({\tfrac {a}{m}})=1,$ mas se $({\tfrac {a}{m}})=1$ não sabemos se $a\ \mathrm {R} \ m$ ou $a\ \mathrm {N} \ m$. Por exemplo: $({\tfrac {2}{15}})=1$ e $({\tfrac {4}{15}})=1$, mas $2\ \mathrm {N} \ 15$ and $4\ \mathrm {R} \ 15$. Se $m$ é primo, os símbolos de Jacobi e Legendre concordam.

Distribuição de resíduos quadráticos

Embora os resíduos quadráticos pareçam ocorrer em um padrão aleatório módulo $n$, e isso tenha sido explorado em aplicações como acústica e criptografia, sua distribuição também exibe algumas regularidades notáveis.

Usando o teorema de Dirichlet sobre primos em progressões aritméticas, a lei da reciprocidade quadrática e o teorema do resto chinês (TCR), é fácil ver que para qualquer $M>0$ existem primos $p$ tais que os números $1,2,...,M$ são todos os resíduos módulo $p$.

Por exemplo, se $p\equiv 1{\pmod {8}}$, $({\text{mod}}\ {12})$, $({\text{mod}}\ {5})$ e $({\text{mod}}\ {28})$, então pela lei da reciprocidade quadrática 2, 3, 5 e 7 serão todos resíduos módulo $p$, e portanto, todos os números de 1 a 10 serão. O TCR diz que isso é o mesmo que $p\equiv 1{\pmod {840}}$, e o teorema de Dirichlet diz que há um número infinito de primos dessa forma. 2521 é o menor e, de fato, $1^{2}\equiv 1,\ 1046^{2}\equiv 2,\ 123^{2}\equiv 3,\ 2^{2}\equiv 4,\ 643^{2}\equiv 5,\ 87^{2}\equiv 6,\ 668^{2}\equiv 7,\ 429^{2}\equiv 8,\ 3^{2}\equiv 9\quad {\text{e}}\quad 529^{2}\equiv 10{\pmod {2521}}$

Fórmulas de Dirichlet

A primeira dessas regularidades deriva do trabalho de Peter Gustav Lejeune Dirichlet (na década de 1830) sobre a fórmula analítica para o número de classe de formas quadráticas binárias. Seja $q$ um número primo, $s$ uma variável complexa, e defina uma função L de Dirichlet como

$L(s)=\sum _{n=1}^{\infty }\left({\frac {n}{q}}\right)n^{-s}.$

Dirichlet mostrou que se $q\equiv 3{\pmod {4}}$, então

$L(1)=-{\frac {\pi }{\sqrt {q}}}\sum _{n=1}^{q-1}{\frac {n}{q}}\left({\frac {n}{q}}\right)>0.$

Portanto, neste caso (primo $q\equiv 3{\pmod {4}}$), a soma dos resíduos quadráticos menos a soma dos não-resíduos no intervalo $1,2,...,q-1$ é um número negativo.

Por exemplo, módulo 11,

${\boldsymbol {1}},2,{\boldsymbol {3}},{\boldsymbol {4}},{\boldsymbol {5}},6,7,8,{\boldsymbol {9}},10$ (resíduos em negrito)

$1+4+9+5+3=22$, $2+6+7+8+10=33$, e a diferença é $-11$.

Na verdade, a diferença sempre será um múltiplo ímpar de $q$ se $q>3$. Em contraste, para o primo $q\equiv 1{\pmod {4}}$, a soma dos resíduos quadráticos menos a soma dos não-resíduos no intervalo $1,2,...,q-1$ é zero, implicando que ambas as somas são iguais ${\frac {q(q-1)}{4}}$.

Dirichlet também provou que para o primo $q\equiv 3{\pmod {4}}$,

$L(1)={\frac {\pi }{\left(2-\left({\frac {2}{q}}\right)\right)\!{\sqrt {q}}}}\sum _{n=1}^{\frac {q-1}{2}}\left({\frac {n}{q}}\right)>0.$

Isso implica que há mais resíduos quadráticos do que não-resíduos entre os números $1,2,...,{\frac {q-1}{2}}$.

Por exemplo, no módulo 11, há quatro resíduos menores que 6 (isto é, 1, 3, 4 e 5), mas apenas um não-resíduo (2).

Um fato intrigante sobre esses dois teoremas é que todas as provas conhecidas dependem de análise; ninguém jamais publicou uma prova simples ou direta de qualquer uma das afirmações.

Lei da reciprocidade quadrática

Ver artigo principal: Lei da reciprocidade quadrática

Se $p$ e $q$ forem primos ímpares, então:

(($p$ é um resíduo quadrático ${\bmod {q}}$) se e somente se ($q$ é um resíduo quadrático${\bmod {p}}$)) se e somente se (pelo menos um de $p$ e $q$ é congruente a $1{\bmod {4}}$).

Isso é:

$\left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{{\frac {p-1}{2}}\cdot {\frac {q-1}{2}}}$

onde $\left({\frac {p}{q}}\right)$ é o símbolo de Legendre.

Assim, para números $a$ e primos ímpares $p$ que não dividem $a$:

a	a é um resíduo quadrático mod p se e somente se	a	a é um resíduo quadrático mod p se e somente se
1	(todo primo p)	−1	p ≡ 1 (mod 4)
2	p ≡ 1, 7 (mod 8)	−2	p ≡ 1, 3 (mod 8)
3	p ≡ 1, 11 (mod 12)	−3	p ≡ 1 (mod 3)
4	(todo primo p)	−4	p ≡ 1 (mod 4)
5	p ≡ 1, 4 (mod 5)	−5	p ≡ 1, 3, 7, 9 (mod 20)
6	p ≡ 1, 5, 19, 23 (mod 24)	−6	p ≡ 1, 5, 7, 11 (mod 24)
7	p ≡ 1, 3, 9, 19, 25, 27 (mod 28)	−7	p ≡ 1, 2, 4 (mod 7)
8	p ≡ 1, 7 (mod 8)	−8	p ≡ 1, 3 (mod 8)
9	(todo primo p)	−9	p ≡ 1 (mod 4)
10	p ≡ 1, 3, 9, 13, 27, 31, 37, 39 (mod 40)	−10	p ≡ 1, 7, 9, 11, 13, 19, 23, 37 (mod 40)
11	p ≡ 1, 5, 7, 9, 19, 25, 35, 37, 39, 43 (mod 44)	−11	p ≡ 1, 3, 4, 5, 9 (mod 11)
12	p ≡ 1, 11 (mod 12)	−12	p ≡ 1 (mod 3)

Pares de resíduos e não-resíduos

Módulo a primo $p$, o número de pares $n$, $n+1$ onde $n\ \mathrm {R} \ p$ e $n+1\ \mathrm {R} \ p$, ou $n\ \mathrm {N} \ p$ e $n+1\ \mathrm {R} \ p$, etc., são quase iguais. Mais precisamente, seja $p$ um primo ímpar. Para $i,j=0,1$ defina os conjuntos

$A_{ij}=\left\{k\in \{1,2,\dots ,p-2\}:\left({\frac {k}{p}}\right)=(-1)^{i}\land \left({\frac {k+1}{p}}\right)=(-1)^{j}\right\},$

e seja

$\alpha _{ij}=|A_{ij}|.$

Isso é,

$\alpha _{00}$ é o número de resíduos que são seguidos por um resíduo,

$\alpha _{01}$ é o número de resíduos que são seguidos por um não-resíduo,

$\alpha _{10}$ é o número de não-resíduos que são seguidos por um resíduo, e

$\alpha _{11}$ é o número de não-resíduos que são seguidos por um não-resíduo.

Então, se $p\equiv 1{\pmod {4}}$

$\alpha _{00}={\frac {p-5}{4}},\;\alpha _{01}=\alpha _{10}=\alpha _{11}={\frac {p-1}{4}}$

e se $p\equiv 3{\pmod {4}}$

$\alpha _{01}={\frac {p+1}{4}},\;\alpha _{00}=\alpha _{10}=\alpha _{11}={\frac {p-3}{4}}.$

Por exemplo: (resíduos em negrito)

Módulo 17

${\boldsymbol {1}},{\boldsymbol {2}},3,{\boldsymbol {4}},5,6,7,{\boldsymbol {8}},{\boldsymbol {9}},10,11,12,{\boldsymbol {13}},14,{\boldsymbol {15}},{\boldsymbol {16}}$

$A_{00}=\{1,8,15\}$,

$A_{01}=\{2,4,9,13\}$,

$A_{10}=\{3,7,12,14\}$,

$A_{11}=\{5,6,10,11\}$.

Módulo 19

${\boldsymbol {1}},2,3,{\boldsymbol {4}},{\boldsymbol {5}},{\boldsymbol {6}},{\boldsymbol {7}},8,{\boldsymbol {9}},10,{\boldsymbol {11}},12,13,14,15,{\boldsymbol {16}},{\boldsymbol {17}},18$

$A_{00}=\{4,5,6,16\}$,

$A_{01}=\{1,7,9,11,17\}$,

$A_{10}=\{3,8,10,15\}$,

$A_{11}=\{2,12,13,14\}$.

Gauss (1828) introduziu esse tipo de contagem ao provar que se $p\equiv 1{\pmod {4}}$ então $x^{4}\equiv 2{\pmod {p}}$ pode ser resolvido se e somente se $p=a^{2}+64b^{2}$.

A desigualdade de Pólya–Vinogradov

Os valores de $({\tfrac {a}{p}})$ para valores consecutivos de uma variável aleatória simulada como um cara ou coroa. Especificamente, Pólya e Vinogradov provaram (independentemente) em 1918 que para qualquer caráter de Dirichlet não principal $\chi (n)$ módulo $q$ e quaisquer inteiros $M$ e $N$,

$\left|\sum _{n=M+1}^{M+N}\chi (n)\right|=O\left({\sqrt {q}}\log q\right),$

em notação grande-O. Configurando

$\chi (n)=\left({\frac {n}{q}}\right),$

isso mostra que o número de resíduos quadráticos módulo $q$ em qualquer intervalo de comprimento $N$ é

${\frac {1}{2}}N+O({\sqrt {q}}\log q).$

É fácil provar que

$\left|\sum _{n=M+1}^{M+N}\left({\frac {n}{q}}\right)\right|<{\sqrt {q}}\log q.$

De fato,

$\left|\sum _{n=M+1}^{M+N}\left({\frac {n}{q}}\right)\right|<{\frac {4}{\pi ^{2}}}{\sqrt {q}}\log q+0.41{\sqrt {q}}+0.61.$

Montgomery e Vaughan melhoraram isso em 1977, mostrando que, se a hipótese generalizada de Riemann for verdadeira, então

$\left|\sum _{n=M+1}^{M+N}\chi (n)\right|=O\left({\sqrt {q}}\log \log q\right).$

Este resultado não pode ser substancialmente melhorado, pois Schur provou em 1918 que

$\max _{N}\left|\sum _{n=1}^{N}\left({\frac {n}{q}}\right)\right|>{\frac {1}{2\pi }}{\sqrt {q}}$

e Paley provou em 1932 que

$\max _{N}\left|\sum _{n=1}^{N}\left({\frac {d}{n}}\right)\right|>{\frac {1}{7}}{\sqrt {d}}\log \log d$

para infinitos $d>0$.

Menor não-resíduo quadrático

O menor resíduo quadrático${\bmod {p}}$ é claramente 1. A questão da magnitude do menor não-resíduo quadrático $n(p)$ é mais sutil, mas é sempre primo.

A desigualdade de Pólya – Vinogradov acima fornece $O({\sqrt {p}}\ \log p)$.

A melhor estimativa incondicional é $n(p)\ll p\theta$ para qualquer $\theta >{\tfrac {1}{4{\sqrt {e}}}}$, obtida por estimativas de Burgess em somas de caracteres.

Assumindo a hipótese generalizada de Riemann, Ankeny obteve $n(p)\ll (\log p)^{2}$.

Linnik mostrou que o número de $p$ menor que $X$ tal que $n(p)>X^{\epsilon }$ é limitado por uma constante dependendo de $\epsilon$.

Os menores não-resíduos quadráticos${\bmod {p}}$ para números primos ímpares $p$ são:

2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, ... (sequência A053760 na OEIS)

Excesso quadrático

Seja $p$ um primo ímpar. O excesso quadrático $E(p)$ é o número de resíduos quadráticos no intervalo $(0,{\tfrac {p}{2}})$ menos o número no intervalo $({\tfrac {p}{2}},p)$ (sequência A178153 na OEIS). Para $p$ congruente a $1{\bmod {4}}$, o excesso é zero, pois $-1$ é um resíduo quadrático e os resíduos são simétricos sob $r\leftrightarrow p-r$. Para $p$ congruente com $3{\bmod {4}}$, o excesso $E$ é sempre positivo.

Complexidade de encontrar raízes quadradas

Ou seja, dado um número $a$ e um módulo $n$, quão difícil é

1. para dizer se existe um $x$ resolvendo $x^{2}\equiv a{\pmod {n}}$
2. assumindo que existe, para calculá-lo?

Uma diferença importante entre os módulos primos e compostos é mostrada aqui. Módulo um primo $p$, um resíduo quadrático $a$ tem $1+(a|p)$ raízes (ou seja, zero se $a\ \mathrm {N} \ p$, um se $a\equiv 0{\pmod {p}}$, ou dois se $a\ \mathrm {R} \ p$ e $\mathrm {mdc} (a,p)=1$.)

Em geral, se um módulo composto $n$ é escrito como um produto de potências de primos distintos, e há $n_{1}$ raízes módulo o primeiro, $n_{2}$ mod o segundo, ..., haverá $n_{1}n_{2}$ ... raízes módulo $n$.

A maneira teórica pela qual as soluções módulo e as potências primas são combinadas para formar as soluções módulo $n$ é chamada de teorema chinês do resto; pode ser implementado com um algoritmo eficiente.

Por exemplo:

Resolva $x^{2}\equiv 6{\pmod {15}}$.

$x^{2}\equiv 6{\pmod {3}}$ tem uma solução, $0$; $x^{2}\equiv 6{\pmod {5}}$ tem dois, $1$ e $4$.

e há duas soluções módulo 15, ou seja, 6 e 9.

Resolva $x^{2}\equiv 4{\pmod {15}}$.

$x^{2}\equiv 4{\pmod {3}}$ tem duas soluções, $1$ e $2$; $x^{2}\equiv 4{\pmod {5}}$ tem dois, $2$ e $3$.

e há quatro soluções módulo 15, isto é, 2, 7, 8 e 13.

Resolva $x^{2}\equiv 7{\pmod {15}}$.

$x^{2}\equiv 7{\pmod {3}}$ tem duas soluções, $1$ e $2$; $x^{2}\equiv 7{\pmod {5}}$ não tem soluções.

e não há soluções módulo 15.

Módulo de primo ou potência de primo

Em primeiro lugar, se o módulo $n$ for primo, o símbolo de Legendre $\left({\frac {a}{n}}\right)$ pode ser rapidamente calculado usando uma variação do algoritmo de Euclides ou o critério de Euler. Se for $-1$, não há solução. Em segundo lugar, assumindo que $\left({\frac {a}{n}}\right)=1$, se $n\equiv 3{\pmod {4}}$, Lagrange descobriu que as soluções são dadas por

$x\equiv \pm \;a^{(n+1)/4}{\pmod {n}},$

e Legendre encontrou uma solução semelhante se $n\equiv 5{\pmod {8}}$:

$x\equiv {\begin{cases}\pm \;a^{(n+3)/8}{\pmod {n}}&{\text{ se }}a{\text{ é um resíduo quártico módulo }}n\\\pm \;a^{(n+3)/8}2^{(n-1)/4}{\pmod {n}}&{\text{ se }}a{\text{ é um não-resíduo quártico módulo }}n\end{cases}}$

Para o primo $n\equiv 1{\pmod {8}}$, entretanto, não há fórmula conhecida. Tonelli (em 1891) e Cipolla encontraram algoritmos eficientes que funcionam para todos os módulos primos. Ambos os algoritmos requerem encontrar um não-resíduo quadrático módulo $n$, e não existe um algoritmo determinístico eficiente conhecido para fazer isso. Mas, uma vez que metade dos números entre $1$ e $n$ são não-resíduos, escolher os números $x$ aleatoriamente e calcular o símbolo de Legendre $\left({\frac {x}{n}}\right)$ até que um não-resíduo seja encontrado, produzirá um rapidamente. Uma ligeira variante desse algoritmo é o algoritmo de Tonelli-Shanks.

Se o módulo $n$ é uma potência prima $n=p^{e}$, uma solução pode ser encontrada módulo $p$ e "elevada" para uma solução módulo $n$ usando o lema de Hensel ou um algoritmo de Gauss.

Módulo composto

Se o módulo $n$ foi fatorado em potências primas, a solução foi discutida acima.

Se $n$ não for congruente com 2 módulo 4 e o símbolo de Kronecker $\left({\tfrac {a}{n}}\right)=-1$ então não há solução; se $n$ for congruente com 2 módulo 4 e $\left({\tfrac {a}{n/2}}\right)=-1$, então também não há solução. Se $n$ não for congruente com 2 módulo 4 e $\left({\tfrac {a}{n}}\right)=1$, ou $n$ é congruente com 2 módulo 4 e $\left({\tfrac {a}{n/2}}\right)=1$, pode ou não haver um.

Se a fatoração completa de $n$ não for conhecida, e $\left({\tfrac {a}{n}}\right)=1$ e $n$ não é congruente com 2 módulo 4, ou $n$ é congruente com 2 módulo 4 e $\left({\tfrac {a}{n/2}}\right)=1$, o problema é conhecido por ser equivalente à fatoração de número inteiro de $n$ (ou seja, uma solução eficiente para qualquer problema poderia ser usada para resolver o outro de forma eficiente).

A discussão acima indica como o conhecimento dos fatores de $n$ nos permite encontrar as raízes com eficiência. Digamos que haja um algoritmo eficiente para encontrar raízes quadradas módulo um número composto. O artigo congruência de quadrados discute como encontrar dois números $x$ e $y$ onde $x^{2}\equiv y^{2}{\pmod {n}}$ e $x\neq \pm y$ é suficiente para fatorar $n$ eficientemente. Gere um número aleatório, eleve ao quadrado módulo $n$ e faça com que o algoritmo de raiz quadrada eficiente encontre uma raiz. Repita até que ele retorne um número diferente daquele que originalmente elevamos ao quadrado (ou seu negativo módulo $n$), então siga o algoritmo descrito em congruência de quadrados. A eficiência do algoritmo de fatoração depende das características exatas do localizador de raízes (por exemplo, ele retorna todas as raízes? Apenas a menor? Uma aleatória?), mas será eficiente.

Determinar se $a$ é um resíduo quadrático ou não-resíduo módulo $n$ (denotado como $a\ \mathrm {R} \ n$ ou $a\ \mathrm {N} \ n$) pode ser feito de forma eficiente para o primo $n$ calculando o símbolo de Legendre. No entanto, para o composto $n$, isso forma o problema de residuosidade quadrática, que não é tão difícil quanto a fatoração, mas é considerado bastante difícil.

Por outro lado, se quisermos saber se existe uma solução para $x$ menor do que algum limite $c$ dado, este problema é NP-completo; entretanto, este é um problema tratável de parâmetro fixo, onde $c$ é o parâmetro.

Em geral, para determinar se $a$ é um resíduo quadrático módulo $n$ composto, pode-se usar o seguinte teorema:

Seja $n>1$ e $\mathrm {mdc} (a,n)=1$. Então $x^{2}\equiv a{\pmod {n}}$ é solucionável se e somente se:

• O símbolo de Legendre $\left({\tfrac {a}{p}}\right)=1$ para todos os divisores primos ímpares $p$ de $n$.
• $a\equiv 1{\pmod {4}}$ se $n$ for divisível por 4, mas não por 8; ou $a\equiv 1{\pmod {8}}$ se $n$ for divisível por 8.

Nota: Este teorema requer essencialmente que a fatoração de $n$ seja conhecida. Observe também que se $\mathrm {mdc} (a,n)=m$, então a congruência pode ser reduzida a ${\tfrac {a}{m}}\equiv {\tfrac {x^{2}}{m}}{\pmod {\tfrac {n}{m}}}$, mas então isso tira o problema dos resíduos quadráticos (a menos que $m$ seja um quadrado).

O número de resíduos quadráticos

A lista do número de resíduos quadráticos módulo $n$, para $n=1,2,3,...$, é semelhante a:

1, 2, 2, 2, 3, 4, 4, 3, 4, 6, 6, 4, 7, 8, 6, ... (sequência A000224 na OEIS)

Uma fórmula para contar o número de quadrados módulo $n$ é dada por Stangl.

Aplicações de resíduos quadráticos

Acústica

Os difusores de som foram baseados em conceitos da teoria dos números, como raízes primitivas e resíduos quadráticos.

Teoria dos grafos

Os grafos de Paley são grafos densos não direcionados, um para cada primo p ≡ 1 (mod 4), que formam uma família infinita de grafos de conferência, que geram uma família infinita de matrizes de conferência simétricas.

Os dígrafos de Paley são análogos dirigidos dos grafos de Paley, um para cada p ≡ 3 (mod 4), que produzem matrizes de conferência anti simétricas.

A construção desses gráficos utiliza resíduos quadráticos.

Criptografia

O fato de encontrar uma raiz quadrada de um módulo de número de um grande composto n é equivalente a fatoração (que é amplamente considerado um problema difícil) tem sido usado para construir esquemas criptográficos, como o criptosistema Rabin e a transferência inconsciente. O problema de residuosidade quadrática é a base do criptosistema Goldwasser–Micali .

O logaritmo discreto é um problema semelhante que também é usado em criptografia.

Teste de primalidade

O critério de Euler é uma fórmula para o símbolo de Legendre (a|p) onde p é primo. Se p for composto, a fórmula pode ou não calcular (a|p) corretamente. O teste de primalidade de Solovay–Strassen, para saber se um determinado número n é primo ou composto, escolhe um a aleatório e calcula (a|n) usando uma modificação do algoritmo de Euclides e também usa o critério de Euler. Se os resultados discordarem, n é composto; se eles concordarem, n pode ser composto ou primo. Para um n composto, pelo menos 1/2 dos valores de a no intervalo 2, 3, ..., n - 1 retornará "n é composto"; para o n primo nenhum o fará. Se, depois de usar muitos valores diferentes de a, n não for provado composto, ele é chamado de "provável primo".

O teste de primalidade de Miller–Rabin é baseado nos mesmos princípios. Há uma versão determinística disso, mas a prova de que funciona depende da hipótese generalizada de Riemann; a saída desse teste é "n é definitivamente composto" ou "ou n é primo ou a hipótese generalizada de Riemann (GRH) é falsa". Se a segunda saída ocorrer para um n composto, a GRH seria falsa, o que teria implicações em muitos ramos da matemática.

Fatoração de inteiros

No § VI do Disquisitiones Arithmeticae Gauss discute dois algoritmos de fatoração que usam resíduos quadráticos e a lei da reciprocidade quadrática.

Vários algoritmos de fatoração modernos (incluindo o algoritmo de Dixon, o método de fração contínua, a peneira quadrática e a peneira de campo numérico) geram pequenos resíduos quadráticos (módulo o número sendo fatorado) em uma tentativa de encontrar uma congruência de quadrados que produzirá uma fatoração. A peneira de campo numérico é o algoritmo de fatoração de propósito geral mais rápido conhecido.

Tabela de resíduos quadráticos

A seguinte tabela (sequência A096008 na OEIS) lista os resíduos quadráticos${\bmod {1}}$ a $75$ (um número vermelho significa que não é coprimo com $n$). (Para os resíduos quadráticos coprimos a $n$, consulte (sequência A096103 na OEIS), e para resíduos quadráticos diferentes de zero, consulte (sequência A046071 na OEIS).)

$n$	resíduos quadráticos mod $n$	$n$	resíduos quadráticos mod $n$	$n$	resíduos quadráticos mod $n$
1	0	26	0, 1, 3, 4, 9, 10, 12, 13, 14, 16, 17, 22, 23, 25	51	0, 1, 4, 9, 13, 15, 16, 18, 19, 21, 25, 30, 33, 34, 36, 42, 43, 49
2	0, 1	27	0, 1, 4, 7, 9, 10, 13, 16, 19, 22, 25	52	0, 1, 4, 9, 12, 13, 16, 17, 25, 29, 36, 40, 48, 49
3	0, 1	28	0, 1, 4, 8, 9, 16, 21, 25	53	0, 1, 4, 6, 7, 9, 10, 11, 13, 15, 16, 17, 24, 25, 28, 29, 36, 37, 38, 40, 42, 43, 44, 46, 47, 49, 52
4	0, 1	29	0, 1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28	54	0, 1, 4, 7, 9, 10, 13, 16, 19, 22, 25, 27, 28, 31, 34, 36, 37, 40, 43, 46, 49, 52
5	0, 1, 4	30	0, 1, 4, 6, 9, 10, 15, 16, 19, 21, 24, 25	55	0, 1, 4, 5, 9, 11, 14, 15, 16, 20, 25, 26, 31, 34, 36, 44, 45, 49
6	0, 1, 3, 4	31	0, 1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28	56	0, 1, 4, 8, 9, 16, 25, 28, 32, 36, 44, 49
7	0, 1, 2, 4	32	0, 1, 4, 9, 16, 17, 25	57	0, 1, 4, 6, 7, 9, 16, 19, 24, 25, 28, 30, 36, 39, 42, 43, 45, 49, 54, 55
8	0, 1, 4	33	0, 1, 3, 4, 9, 12, 15, 16, 22, 25, 27, 31	58	0, 1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28, 29, 30, 33, 34, 35, 36, 38, 42, 45, 49, 51, 52, 53, 54, 57
9	0, 1, 4, 7	34	0, 1, 2, 4, 8, 9, 13, 15, 16, 17, 18, 19, 21, 25, 26, 30, 32, 33	59	0, 1, 3, 4, 5, 7, 9, 12, 15, 16, 17, 19, 20, 21, 22, 25, 26, 27, 28, 29, 35, 36, 41, 45, 46, 48, 49, 51, 53, 57
10	0, 1, 4, 5, 6, 9	35	0, 1, 4, 9, 11, 14, 15, 16, 21, 25, 29, 30	60	0, 1, 4, 9, 16, 21, 24, 25, 36, 40, 45, 49
11	0, 1, 3, 4, 5, 9	36	0, 1, 4, 9, 13, 16, 25, 28	61	0, 1, 3, 4, 5, 9, 12, 13, 14, 15, 16, 19, 20, 22, 25, 27, 34, 36, 39, 41, 42, 45, 46, 47, 48, 49, 52, 56, 57, 58, 60
12	0, 1, 4, 9	37	0, 1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36	62	0, 1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28, 31, 32, 33, 35, 36, 38, 39, 40, 41, 45, 47, 49, 50, 51, 56, 59
13	0, 1, 3, 4, 9, 10, 12	38	0, 1, 4, 5, 6, 7, 9, 11, 16, 17, 19, 20, 23, 24, 25, 26, 28, 30, 35, 36	63	0, 1, 4, 7, 9, 16, 18, 22, 25, 28, 36, 37, 43, 46, 49, 58
14	0, 1, 2, 4, 7, 8, 9, 11	39	0, 1, 3, 4, 9, 10, 12, 13, 16, 22, 25, 27, 30, 36	64	0, 1, 4, 9, 16, 17, 25, 33, 36, 41, 49, 57
15	0, 1, 4, 6, 9, 10	40	0, 1, 4, 9, 16, 20, 24, 25, 36	65	0, 1, 4, 9, 10, 14, 16, 25, 26, 29, 30, 35, 36, 39, 40, 49, 51, 55, 56, 61, 64
16	0, 1, 4, 9	41	0, 1, 2, 4, 5, 8, 9, 10, 16, 18, 20, 21, 23, 25, 31, 32, 33, 36, 37, 39, 40	66	0, 1, 3, 4, 9, 12, 15, 16, 22, 25, 27, 31, 33, 34, 36, 37, 42, 45, 48, 49, 55, 58, 60, 64
17	0, 1, 2, 4, 8, 9, 13, 15, 16	42	0, 1, 4, 7, 9, 15, 16, 18, 21, 22, 25, 28, 30, 36, 37, 39	67	0, 1, 4, 6, 9, 10, 14, 15, 16, 17, 19, 21, 22, 23, 24, 25, 26, 29, 33, 35, 36, 37, 39, 40, 47, 49, 54, 55, 56, 59, 60, 62, 64, 65
18	0, 1, 4, 7, 9, 10, 13, 16	43	0, 1, 4, 6, 9, 10, 11, 13, 14, 15, 16, 17, 21, 23, 24, 25, 31, 35, 36, 38, 40, 41	68	0, 1, 4, 8, 9, 13, 16, 17, 21, 25, 32, 33, 36, 49, 52, 53, 60, 64
19	0, 1, 4, 5, 6, 7, 9, 11, 16, 17	44	0, 1, 4, 5, 9, 12, 16, 20, 25, 33, 36, 37	69	0, 1, 3, 4, 6, 9, 12, 13, 16, 18, 24, 25, 27, 31, 36, 39, 46, 48, 49, 52, 54, 55, 58, 64
20	0, 1, 4, 5, 9, 16	45	0, 1, 4, 9, 10, 16, 19, 25, 31, 34, 36, 40	70	0, 1, 4, 9, 11, 14, 15, 16, 21, 25, 29, 30, 35, 36, 39, 44, 46, 49, 50, 51, 56, 60, 64, 65
21	0, 1, 4, 7, 9, 15, 16, 18	46	0, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18, 23, 24, 25, 26, 27, 29, 31, 32, 35, 36, 39, 41	71	0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 19, 20, 24, 25, 27, 29, 30, 32, 36, 37, 38, 40, 43, 45, 48, 49, 50, 54, 57, 58, 60, 64
22	0, 1, 3, 4, 5, 9, 11, 12, 14, 15, 16, 20	47	0, 1, 2, 3, 4, 6, 7, 8, 9, 12, 14, 16, 17, 18, 21, 24, 25, 27, 28, 32, 34, 36, 37, 42	72	0, 1, 4, 9, 16, 25, 28, 36, 40, 49, 52, 64
23	0, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18	48	0, 1, 4, 9, 16, 25, 33, 36	73	0, 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 19, 23, 24, 25, 27, 32, 35, 36, 37, 38, 41, 46, 48, 49, 50, 54, 55, 57, 61, 64, 65, 67, 69, 70, 71, 72
24	0, 1, 4, 9, 12, 16	49	0, 1, 2, 4, 8, 9, 11, 15, 16, 18, 22, 23, 25, 29, 30, 32, 36, 37, 39, 43, 44, 46	74	0, 1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36, 37, 38, 40, 41, 44, 46, 47, 48, 49, 53, 58, 62, 63, 64, 65, 67, 70, 71, 73
25	0, 1, 4, 6, 9, 11, 14, 16, 19, 21, 24	50	0, 1, 4, 6, 9, 11, 14, 16, 19, 21, 24, 25, 26, 29, 31, 34, 36, 39, 41, 44, 46, 49	75	0, 1, 4, 6, 9, 16, 19, 21, 24, 25, 31, 34, 36, 39, 46, 49, 51, 54, 61, 64, 66, 69

Resíduos Quadráticos (consulte também (sequência A048152 na OEIS), (sequência A343720 na OEIS))

x	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
x2	1	4	9	16	25	36	49	64	81	100	121	144	169	196	225	256	289	324	361	400	441	484	529	576	625
mod 1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
mod 2	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
mod 3	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1
mod 4	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
mod 5	1	4	4	1	0	1	4	4	1	0	1	4	4	1	0	1	4	4	1	0	1	4	4	1	0
mod 6	1	4	3	4	1	0	1	4	3	4	1	0	1	4	3	4	1	0	1	4	3	4	1	0	1
mod 7	1	4	2	2	4	1	0	1	4	2	2	4	1	0	1	4	2	2	4	1	0	1	4	2	2
mod 8	1	4	1	0	1	4	1	0	1	4	1	0	1	4	1	0	1	4	1	0	1	4	1	0	1
mod 9	1	4	0	7	7	0	4	1	0	1	4	0	7	7	0	4	1	0	1	4	0	7	7	0	4
mod 10	1	4	9	6	5	6	9	4	1	0	1	4	9	6	5	6	9	4	1	0	1	4	9	6	5
mod 11	1	4	9	5	3	3	5	9	4	1	0	1	4	9	5	3	3	5	9	4	1	0	1	4	9
mod 12	1	4	9	4	1	0	1	4	9	4	1	0	1	4	9	4	1	0	1	4	9	4	1	0	1
mod 13	1	4	9	3	12	10	10	12	3	9	4	1	0	1	4	9	3	12	10	10	12	3	9	4	1
mod 14	1	4	9	2	11	8	7	8	11	2	9	4	1	0	1	4	9	2	11	8	7	8	11	2	9
mod 15	1	4	9	1	10	6	4	4	6	10	1	9	4	1	0	1	4	9	1	10	6	4	4	6	10
mod 16	1	4	9	0	9	4	1	0	1	4	9	0	9	4	1	0	1	4	9	0	9	4	1	0	1
mod 17	1	4	9	16	8	2	15	13	13	15	2	8	16	9	4	1	0	1	4	9	16	8	2	15	13
mod 18	1	4	9	16	7	0	13	10	9	10	13	0	7	16	9	4	1	0	1	4	9	16	7	0	13
mod 19	1	4	9	16	6	17	11	7	5	5	7	11	17	6	16	9	4	1	0	1	4	9	16	6	17
mod 20	1	4	9	16	5	16	9	4	1	0	1	4	9	16	5	16	9	4	1	0	1	4	9	16	5
mod 21	1	4	9	16	4	15	7	1	18	16	16	18	1	7	15	4	16	9	4	1	0	1	4	9	16
mod 22	1	4	9	16	3	14	5	20	15	12	11	12	15	20	5	14	3	16	9	4	1	0	1	4	9
mod 23	1	4	9	16	2	13	3	18	12	8	6	6	8	12	18	3	13	2	16	9	4	1	0	1	4
mod 24	1	4	9	16	1	12	1	16	9	4	1	0	1	4	9	16	1	12	1	16	9	4	1	0	1
mod 25	1	4	9	16	0	11	24	14	6	0	21	19	19	21	0	6	14	24	11	0	16	9	4	1	0

Ver também

• Critério de Euler
• Lei da reciprocidade quadrática

Referências

O Disquisitiones Arithmeticae foi traduzido do latim ciceroniano de Gauss para o inglês e o alemão. A edição alemã inclui todos os seus artigos sobre a teoria dos números: todas as provas de reciprocidade quadrática, a determinação do sinal da soma de Gauss, as investigações sobre a reciprocidade biquadrática e notas não publicadas.

• Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithemeticae, ISBN 0-387-96254-9 Second corrected ed. , New York: Springer 
• Gauss, Carl Friedrich; Maser, H. (translator into German) (1965), Untersuchungen über hohere Arithmetik [Disquisitiones Arithemeticae & other papers on number theory], ISBN 0-8284-0191-8 second ed. , New York: Chelsea 
• Bach, Eric; Shallit, Jeffrey (1996), Efficient Algorithms, ISBN 0-262-02405-5, Algorithmic Number Theory, I, Cambridge: MIT Press 
• Crandall, Richard; Pomerance, Carl (2001), Prime Numbers: A Computational Perspective, ISBN 0-387-94777-9, New York: Springer 
• Davenport, Harold (2000), Multiplicative Number Theory, ISBN 0-387-95097-4 third ed. , New York: Springer 
• Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, ISBN 0-7167-1045-5, W. H. Freeman  A7.1: AN1, pg.249.
• Hardy, G. H.; Wright, E. M. (1980), An Introduction to the Theory of Numbers, ISBN 978-0-19-853171-5 fifth ed. , Oxford: Oxford University Press 
• Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory, ISBN 0-387-97329-X second ed. , New York: Springer 
• Lemmermeyer, Franz (2000), Reciprocity Laws: from Euler to Eisenstein, ISBN 3-540-66957-4, Berlin: Springer 
• Manders, Kenneth L.; Adleman, Leonard (1978), «NP-Complete Decision Problems for Binary Quadratics», Journal of Computer and System Sciences, 16 (2): 168–184, doi:10.1016/0022-0000(78)90044-2. 

Ligações externas

• Weisstein, Eric W. «Quadratic Residue» (em inglês). MathWorld 
• Prova da desigualdade Pólya–Vinogradov em PlanetMath.org.