Resíduo quadrático

Predefinição:Má tradução 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(\mathrm{mod}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(\mathrm{mod}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 corpo $\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(\mathrm{mod}4)$ então $-1$ é um resíduo quadrático módulo $p$, e se $p\equiv 3(\mathrm{mod}4)$ então $-1$ é um não-resíduo quadrático módulo $p$. Isso implica o seguinte:

Se $p\equiv 1(\mathrm{mod}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(\mathrm{mod}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(\mathrm{mod}8)$ e, portanto, também $\equiv 1(\mathrm{mod}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(\mathrm{mod}8)$.Predefinição:QuotePortanto, um número diferente de zero é um resíduo $mod8$, $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\ge 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 $modp$; $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 $\ge 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.Predefinição:QuoteAlém disso, o produto de dois não-resíduos pode ser um resíduo, um não-resíduo ou zero.Predefinição:QuoteEste 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 $\mathrm{Z}/n\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 $\mathrm{Z}/n\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{array}{cc}0& \text{ se }p\text{ divide }a\\ +1& \text{ se }a\mathrm{R}p\text{ e }p\text{ não divide }a\\ -1& \text{ se }a\mathrm{N}p\text{ e }p\text{ não divide }a\end{array}$

Existem duas razões pelas quais os números $\equiv 0(\mathrm{mod}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 $(\frac{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 $(\frac{a}{m})=-1,$ então $a\mathrm{N}m$, e se $a\mathrm{R}m$ então $(\frac{a}{m})=1,$ mas se $(\frac{a}{m})=1$ não sabemos se $a\mathrm{R}m$ ou $a\mathrm{N}m$. Por exemplo: $(\frac{2}{15})=1$ e $(\frac{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$.Predefinição:Quote

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}^{\mathrm{\infty }}\left(\frac{n}{q}\right)n^{-s}.$

Dirichlet mostrou que se $q\equiv 3(\mathrm{mod}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(\mathrm{mod}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,

$1,2,3,4,5,6,7,8,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(\mathrm{mod}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}$

.Predefinição:Cn

Dirichlet também provou que para o primo $q\equiv 3(\mathrm{mod}4)$,

$L(1)=\frac{\pi }{(2-\left(\frac{2}{q}\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}$.Predefinição:QuoteUm 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

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

(($p$ é um resíduo quadrático $modq$) se e somente se ($q$ é um resíduo quadrático$modp$)) se e somente se (pelo menos um de $p$ e $q$ é congruente a $1mod4$).

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}=\{k\in \{1,2,\dots ,p-2\}:\left(\frac{k}{p}\right)=(-1{)}^i\wedge \left(\frac{k+1}{p}\right)=(-1{)}^j\},$

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(\mathrm{mod}4)$

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

e se $p\equiv 3(\mathrm{mod}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

$1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,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

$1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,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(\mathrm{mod}4)$

então

$x^4\equiv 2(\mathrm{mod}p)$

pode ser resolvido se e somente se

$p=a^2+64b^2$

.

A desigualdade de Pólya–Vinogradov

Os valores de $(\frac{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$,

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

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

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

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

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

e Paley provou em 1932 que

$\underset{N}{\max }\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$modp$ é 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 >\frac{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^{ϵ}$ é limitado por uma constante dependendo de $ϵ$.

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

2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, ... Predefinição: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,\frac{p}{2})$ menos o número no intervalo $(\frac{p}{2},p)$ Predefinição:OEIS. Para $p$ congruente a $1mod4$, 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 $3mod4$, 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(\mathrm{mod}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(\mathrm{mod}p)$, ou dois se $a\mathrm{R}p$ e $\mathrm{m}\mathrm{d}\mathrm{c}(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.Predefinição:Quote

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(\mathrm{mod}4)$, Lagrange descobriu que as soluções são dadas por

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

e Legendre encontrou uma solução semelhante se $n\equiv 5(\mathrm{mod}8)$:

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

Para o primo $n\equiv 1(\mathrm{mod}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(\frac{a}{n}\right)=-1$ então não há solução; se $n$ for congruente com 2 módulo 4 e $\left(\frac{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(\frac{a}{n}\right)=1$, ou $n$ é congruente com 2 módulo 4 e $\left(\frac{a}{n/2}\right)=1$, pode ou não haver um.

Se a fatoração completa de $n$ não for conhecida, e $\left(\frac{a}{n}\right)=1$ e $n$ não é congruente com 2 módulo 4, ou $n$ é congruente com 2 módulo 4 e $\left(\frac{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).Predefinição:QuoteDeterminar 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{m}\mathrm{d}\mathrm{c}(a,n)=1$. Então $x^2\equiv a(\mathrm{mod}n)$ é solucionável se e somente se:

• O símbolo de Legendre $\left(\frac{a}{p}\right)=1$ para todos os divisores primos ímpares $p$ de $n$.
• $a\equiv 1(\mathrm{mod}4)$ se $n$ for divisível por 4, mas não por 8; ou $a\equiv 1(\mathrm{mod}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{m}\mathrm{d}\mathrm{c}(a,n)=m$, então a congruência pode ser reduzida a $\frac{a}{m}\equiv \frac{x^2}{m}(\mathrm{mod}\frac{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, ... Predefinição: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 Predefinição:OEIS lista os resíduos quadráticos$mod1$ a $75$ (um número vermelho significa que não é coprimo com $n$). (Para os resíduos quadráticos coprimos a $n$, consulte Predefinição:OEIS, e para resíduos quadráticos diferentes de zero, consulte Predefinição: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	Predefinição:Color, 1, 3, Predefinição:Color, 9, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, 17, Predefinição:Color, 23, 25	51	Predefinição:Color, 1, 4, Predefinição:Color, 13, Predefinição:Color, 16, Predefinição:Color, 19, Predefinição:Color, 25, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, 43, 49
2	Predefinição:Color, 1	27	Predefinição:Color, 1, 4, 7, Predefinição:Color, 10, 13, 16, 19, 22, 25	52	Predefinição:Color, 1, Predefinição:Color, 9, Predefinição:Color, Predefinição:Color, Predefinição:Color, 17, 25, 29, Predefinição:Color, Predefinição:Color, Predefinição:Color, 49
3	Predefinição:Color, 1	28	Predefinição:Color, 1, Predefinição:Color, Predefinição:Color, 9, Predefinição:Color, Predefinição:Color, 25	53	Predefinição:Color, 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	Predefinição:Color, 1	29	Predefinição:Color, 1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28	54	Predefinição:Color, 1, Predefinição:Color, 7, Predefinição:Color, Predefinição:Color, 13, Predefinição:Color, 19, Predefinição:Color, 25, Predefinição:Color, Predefinição:Color, 31, Predefinição:Color, Predefinição:Color, 37, Predefinição:Color, 43, Predefinição:Color, 49, Predefinição:Color
5	Predefinição:Color, 1, 4	30	Predefinição:Color, 1, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, 19, Predefinição:Color, Predefinição:Color, Predefinição:Color	55	Predefinição:Color, 1, 4, Predefinição:Color, 9, Predefinição:Color, 14, Predefinição:Color, 16, Predefinição:Color, Predefinição:Color, 26, 31, 34, 36, Predefinição:Color, Predefinição:Color, 49
6	Predefinição:Color, 1, Predefinição:Color, Predefinição:Color	31	Predefinição:Color, 1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28	56	Predefinição:Color, 1, Predefinição:Color, Predefinição:Color, 9, Predefinição:Color, 25, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color
7	Predefinição:Color, 1, 2, 4	32	Predefinição:Color, 1, Predefinição:Color, 9, Predefinição:Color, 17, 25	57	Predefinição:Color, 1, 4, Predefinição:Color, 7, Predefinição:Color, 16, Predefinição:Color, Predefinição:Color, 25, 28, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, 43, Predefinição:Color, 49, Predefinição:Color, 55
8	Predefinição:Color, 1, Predefinição:Color	33	Predefinição:Color, 1, Predefinição:Color, 4, Predefinição:Color, Predefinição:Color, Predefinição:Color, 16, Predefinição:Color, 25, Predefinição:Color, 31	58	Predefinição:Color, 1, Predefinição:Color, 5, Predefinição:Color, 7, 9, 13, Predefinição:Color, Predefinição:Color, Predefinição:Color, 23, Predefinição:Color, 25, Predefinição:Color, Predefinição:Color, Predefinição:Color, 33, Predefinição:Color, 35, Predefinição:Color, Predefinição:Color, Predefinição:Color, 45, 49, 51, Predefinição:Color, 53, Predefinição:Color, 57
9	Predefinição:Color, 1, 4, 7	34	Predefinição:Color, 1, Predefinição:Color, Predefinição:Color, Predefinição:Color, 9, 13, 15, Predefinição:Color, Predefinição:Color, Predefinição:Color, 19, 21, 25, Predefinição:Color, Predefinição:Color, Predefinição:Color, 33	59	Predefinição:Color, 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	Predefinição:Color, 1, Predefinição:Color, Predefinição:Color, Predefinição:Color, 9	35	Predefinição:Color, 1, 4, 9, 11, Predefinição:Color, Predefinição:Color, 16, Predefinição:Color, Predefinição:Color, 29, Predefinição:Color	60	Predefinição:Color, 1, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, 49
11	Predefinição:Color, 1, 3, 4, 5, 9	36	Predefinição:Color, 1, Predefinição:Color, Predefinição:Color, 13, Predefinição:Color, 25, Predefinição:Color	61	Predefinição:Color, 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	Predefinição:Color, 1, Predefinição:Color, Predefinição:Color	37	Predefinição:Color, 1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36	62	Predefinição:Color, 1, Predefinição:Color, Predefinição:Color, 5, 7, Predefinição:Color, 9, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, 19, Predefinição:Color, 25, Predefinição:Color, Predefinição:Color, Predefinição:Color, 33, 35, Predefinição:Color, Predefinição:Color, 39, Predefinição:Color, 41, 45, 47, 49, Predefinição:Color, 51, Predefinição:Color, 59
13	Predefinição:Color, 1, 3, 4, 9, 10, 12	38	Predefinição:Color, 1, Predefinição:Color, 5, Predefinição:Color, 7, 9, 11, Predefinição:Color, 17, Predefinição:Color, Predefinição:Color, 23, Predefinição:Color, 25, Predefinição:Color, Predefinição:Color, Predefinição:Color, 35, Predefinição:Color	63	Predefinição:Color, 1, 4, Predefinição:Color, Predefinição:Color, 16, Predefinição:Color, 22, 25, Predefinição:Color, Predefinição:Color, 37, 43, 46, Predefinição:Color, 58
14	Predefinição:Color, 1, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, 9, 11	39	Predefinição:Color, 1, Predefinição:Color, 4, Predefinição:Color, 10, Predefinição:Color, Predefinição:Color, 16, 22, 25, Predefinição:Color, Predefinição:Color, Predefinição:Color	64	Predefinição:Color, 1, Predefinição:Color, 9, Predefinição:Color, 17, 25, 33, Predefinição:Color, 41, 49, 57
15	Predefinição:Color, 1, 4, Predefinição:Color, Predefinição:Color, Predefinição:Color	40	Predefinição:Color, 1, Predefinição:Color, 9, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color	65	Predefinição:Color, 1, 4, 9, Predefinição:Color, 14, 16, Predefinição:Color, Predefinição:Color, 29, Predefinição:Color, Predefinição:Color, 36, Predefinição:Color, Predefinição:Color, 49, 51, Predefinição:Color, 56, 61, 64
16	Predefinição:Color, 1, Predefinição:Color, 9	41	Predefinição:Color, 1, 2, 4, 5, 8, 9, 10, 16, 18, 20, 21, 23, 25, 31, 32, 33, 36, 37, 39, 40	66	Predefinição:Color, 1, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, 25, Predefinição:Color, 31, Predefinição:Color, Predefinição:Color, Predefinição:Color, 37, Predefinição:Color, Predefinição:Color, Predefinição:Color, 49, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color
17	Predefinição:Color, 1, 2, 4, 8, 9, 13, 15, 16	42	Predefinição:Color, 1, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, 25, Predefinição:Color, Predefinição:Color, Predefinição:Color, 37, Predefinição:Color	67	Predefinição:Color, 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	Predefinição:Color, 1, Predefinição:Color, 7, Predefinição:Color, Predefinição:Color, 13, Predefinição:Color	43	Predefinição:Color, 1, 4, 6, 9, 10, 11, 13, 14, 15, 16, 17, 21, 23, 24, 25, 31, 35, 36, 38, 40, 41	68	Predefinição:Color, 1, Predefinição:Color, Predefinição:Color, 9, 13, Predefinição:Color, Predefinição:Color, 21, 25, Predefinição:Color, 33, Predefinição:Color, 49, Predefinição:Color, 53, Predefinição:Color, Predefinição:Color
19	Predefinição:Color, 1, 4, 5, 6, 7, 9, 11, 16, 17	44	Predefinição:Color, 1, Predefinição:Color, 5, 9, Predefinição:Color, Predefinição:Color, Predefinição:Color, 25, Predefinição:Color, Predefinição:Color, 37	69	Predefinição:Color, 1, Predefinição:Color, 4, Predefinição:Color, Predefinição:Color, Predefinição:Color, 13, 16, Predefinição:Color, Predefinição:Color, 25, Predefinição:Color, 31, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, 49, 52, Predefinição:Color, 55, 58, 64
20	Predefinição:Color, 1, Predefinição:Color, Predefinição:Color, 9, Predefinição:Color	45	Predefinição:Color, 1, 4, Predefinição:Color, Predefinição:Color, 16, 19, Predefinição:Color, 31, 34, Predefinição:Color, Predefinição:Color	70	Predefinição:Color, 1, Predefinição:Color, 9, 11, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, 29, Predefinição:Color, Predefinição:Color, Predefinição:Color, 39, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, 51, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color
21	Predefinição:Color, 1, 4, Predefinição:Color, Predefinição:Color, Predefinição:Color, 16, Predefinição:Color	46	Predefinição:Color, 1, Predefinição:Color, 3, Predefinição:Color, Predefinição:Color, Predefinição:Color, 9, Predefinição:Color, 13, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, 25, Predefinição:Color, 27, 29, 31, Predefinição:Color, 35, Predefinição:Color, 39, 41	71	Predefinição:Color, 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	Predefinição:Color, 1, 3, Predefinição:Color, 5, 9, Predefinição:Color, Predefinição:Color, Predefinição:Color, 15, Predefinição:Color, Predefinição:Color	47	Predefinição:Color, 1, 2, 3, 4, 6, 7, 8, 9, 12, 14, 16, 17, 18, 21, 24, 25, 27, 28, 32, 34, 36, 37, 42	72	Predefinição:Color, 1, Predefinição:Color, Predefinição:Color, Predefinição:Color, 25, Predefinição:Color, Predefinição:Color, Predefinição:Color, 49, Predefinição:Color, Predefinição:Color
23	Predefinição:Color, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18	48	Predefinição:Color, 1, Predefinição:Color, Predefinição:Color, Predefinição:Color, 25, Predefinição:Color, Predefinição:Color	73	Predefinição:Color, 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	Predefinição:Color, 1, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color	49	Predefinição:Color, 1, 2, 4, 8, 9, 11, 15, 16, 18, 22, 23, 25, 29, 30, 32, 36, 37, 39, 43, 44, 46	74	Predefinição:Color, 1, 3, Predefinição:Color, 7, 9, Predefinição:Color, 11, Predefinição:Color, Predefinição:Color, 21, 25, Predefinição:Color, 27, Predefinição:Color, Predefinição:Color, 33, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, Predefinição:Color, 41, Predefinição:Color, Predefinição:Color, 47, Predefinição:Color, 49, 53, Predefinição:Color, Predefinição:Color, 63, Predefinição:Color, 65, 67, Predefinição:Color, 71, 73
25	Predefinição:Color, 1, 4, 6, 9, 11, 14, 16, 19, 21, 24	50	Predefinição:Color, 1, Predefinição:Color, Predefinição:Color, 9, 11, Predefinição:Color, Predefinição:Color, 19, 21, Predefinição:Color, Predefinição:Color, Predefinição:Color, 29, 31, Predefinição:Color, Predefinição:Color, 39, 41, Predefinição:Color, Predefinição:Color, 49	75	Predefinição:Color, 1, 4, Predefinição:Color, Predefinição:Color, 16, 19, Predefinição:Color, Predefinição:Color, Predefinição:Color, 31, 34, Predefinição:Color, Predefinição:Color, 46, 49, Predefinição:Color, Predefinição:Color, 61, 64, Predefinição:Color, Predefinição:Color

Resíduos Quadráticos (consulte também Predefinição:OEIS, Predefinição: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.

• Predefinição:Citation
• Predefinição:Citation
• Predefinição:Citation
• Predefinição:Citation
• Predefinição:Citation
• Predefinição:Citation A7.1: AN1, pg.249.
• Predefinição:Citation
• Predefinição:Citation
• Predefinição:Citation
• Predefinição:Citation

Ligações externas

• Predefinição:MathWorld
• Predefinição:URL