Residuo cadrático

En teoría de números, un número enteiro q chámase residuo cadrático módulo n se é congruente cun cadrado perfecto módulo n; é dicir, se existe un número enteiro x tal que:

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

En caso contrario, q sería non residuo cadrático módulo n.

Historia, convencións e feitos elementais

Fermat, Euler, Lagrange, Legendre e outros teóricos dos números dos séculos XVII e XVIII xa estableceron teoremas e formaron conxecturas sobre residuos cadráticos, mais o primeiro tratamento sistemático é o § IV das Disquisitiones Arithmeticae de Gauss (1801). O artigo 95 introduce a terminoloxía «residuo cadrático» e «non residuo cadrático», e establece que se o contexto o deixa claro, poderá abandonarse o adxectivo «cadrático».

Pódese obter unha lista dos residuos cadráticos módulo n simplemente calculando o cadrado dos números 0, 1,... , n − 1. Debido a que a² ≡ (n − a)² (mod n), a lista de cadrados módulo n é simétrica en relación a n /2. Isto pódese ver na táboa de abaixo.

Módulo un número primo

Módulo un número primo impar p hai (p + 1)/2 residuos (incluíndo 0) e (p - 1)/2 non residuos, segundo o criterio de Euler.

É habitual traballar sen considerar o 0.

Seguindo esta convención, o inverso multiplicativo dun residuo é un residuo e o inverso dun non residuo é un non residuo.

Sen o 0, módulo un número primo impar hai un número igual de residuos e non residuos.

Se p ≡ 1 (mod 4) o negativo dun residuo módulo p é un residuo e o negativo dun non residuo é un non residuo.

O primeiro suplemento á lei da reciprocidade cadrática é que se p ≡ 1 (mod 4) entón −1 é un residuo cadrático módulo p, e se p ≡ 3 (mod 4) entón −1 é un non residuo módulo p. Isto implica o seguinte:

Se p ≡ 3 (mod 4) o negativo dun residuo módulo p é un non residuo e o negativo dun non residuo é un residuo.

Módulos de potencias de primos

Todos os cadrados dos impares son ≡ 1 (mod 8) e, polo tanto, tamén ≡ 1 (mod 4). Se a é un número impar e m = 2ⁿ, n > 2, daquela a é un residuo módulo m se e só se a ≡ 1 (mod 8).

Por exemplo, mod (32=2⁵) os cadrados dos impares son

1² ≡ 15² ≡ 1

3² ≡ 13² ≡ 9

5² ≡ 11² ≡ 25

7² ≡ 9² ≡ 49 ≡ 17

e os cadrados dos pares son

0² ≡ 8² ≡ 16² ≡ 0

2² ≡ 6² ≡ 10² ≡ 14 ² ≡ 4

4² ≡ 12² ≡ 16.

Polo tanto, un número distinto de cero é un residuo mod 2ⁿ, n > 2, se e só se é da forma 4^k (8 n + 1).

Un número a coprimo a un primo impar p é un residuo módulo calquera potencia de p se e só se é un residuo módulo p.

Cando o módulo é pⁿ, temos que p^ka

é un residuo módulo pⁿ se k ≥ n

é un non residuo módulo pⁿ se k < n é impar

é un residuo módulo pⁿ se k < n é par e a é un residuo

é un non residuo módulo pⁿ se k < n é par e a é un non residuo.

Teña en conta que as regras son diferentes para potencias de dous e potencias de primos impares.

Módulo unha potencia dun primo impar n = p^k, os produtos de residuos e non residuos relativamente primos para p obedecen as mesmas regras que o visto para mod p; p é un non residuo e, en xeral, todos os residuos e non residuos obedecen ás mesmas regras, excepto que os produtos serán cero se a potencia de p no produto é ≥ n.

Módulo números compostos que non son unha potencia dun primo

Neste caso temos dous feitos básicos:

Se a é un residuo módulo n, entón a é un residuo módulo $p^{k}$ para toda potencia de primo que divida a n.

Se a é un non residuo módulo n, entón a é un non residuo módulo p^k para polo menos unha potencia de primo que divida a n.

Modulo un número composto hai tres posibilidades:

O produto de dous residuos é un residuo.

O produto dun residuo e un non residuo pode ser un residuo, un non residuo ou cero.

O produto de dous non residuos pode ser un residuo, un non residuo ou cero.

Exemplos:

A partir da táboa de módulo 6: 1, 2, 3, 4, 5 (residuos en grosa). O produto do residuo 3 e do non residuo 5 é o residuo 3, mentres que o produto do residuo 4 e do non residuo 2 é o non residuo 2.

.

A partir da táboa do módulo 15: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 (residuos en grosa). O produto dos non residuos 2 e 8 é o residuo 1, mentres que o produto dos non residuos 2 e 7 é o non residuo 14.

Por esta razón algúns autores engaden á definición de que un residuo cadrático a non só debe ser un cadrado senón que tamén debe ser coprimo co módulo n.

Notacións

Gauss utilizou as letras R e N para indicar residuos e non residuos, respectivamente;

por exemplo, 2 R 7 e 5 N 7, ou 1 R 8 e 3 N 8.

Aínda que esta notación é compacta e conveniente para algúns propósitos, unha notación máis útil é o símbolo de Legendre, tamén chamado carácter cadrático, que se define para todos os números enteiros a e números primos impares 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{ non divide }}a\\-1&{\text{se }}a\operatorname {N} p{\text{ e }}p{\text{ non divide }}a\end{cases}}$

Hai dúas razóns polas que se tratan especialmente os números ≡ 0 (mod p). Como vimos, facilita a formulación de moitas fórmulas e teoremas. A outra razón (relacionada con esta) é que o carácter cadrático é un homomorfismo entre o grupo multiplicativo de enteiros distintos de cero módulo p e os números complexos baixo multiplicación. Definindo $({\tfrac {np}{p}})=0$ podemos estender o seu dominio ao semigrupo multiplicativo de todos os números enteiros.

Unha vantaxe desta notación sobre a de Gauss é que o símbolo de Legendre é unha función que se pode usar nas fórmulas. Tamén se pode xeneralizar facilmente a residuos dunha potencia maior.

Co tempo os símbolos de Legendre foron xeneralizándose:

Símbolo de Jacobi: sexa a un número enteiro e n un número natural impar, con factorización $n=p_{1}^{e_{1}}\cdots p_{k}^{e_{k}},$ o símbolo de Jacobi sería:

$\left({\frac {a}{n}}\right)=\prod _{i=1}^{k}\left({\frac {a}{p_{i}}}\right)^{e_{i}}$

sendo $\textstyle \left({\frac {a}{p_{i}}}\right)$ o símbolo de Legendre. Cando n é un número primo impar, os símbolo de Jacobi e de Legendre coinciden.

Símbolo de Kronecker: sexa $n$ un enteiro distinto de 0, con factorización $n=u\cdot p_{1}^{e_{1}}\cdots p_{k}^{e_{k}},$ onde $u=\pm 1$. Sexa $a$ un enteiro, o símbolo de Kronecker sería:

$\left({\frac {a}{n}}\right):=\left({\frac {a}{u}}\right)\prod _{i=1}^{k}\left({\frac {a}{p_{i}}}\right)^{e_{i}}.$

E nos tres casos con cadansúa lei de reciprocidade cadrática.

Distribución dos residuos cadráticos

Existen certas regularidades na distribución dos residuos cadráticos.

A primeira destas regularidades provén do traballo de Peter Gustav Lejeune Dirichlet (na década de 1830) sobre a fórmula analítica para o número de clase das formas cadráticas binarias. Sexa q un número primo, s unha variábel complexa e definimos unha función L de Dirichlet como

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

Dirichlet demostrou que se q ≡ 3 (mod 4), daquela

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

Polo tanto, neste caso, a suma dos residuos cadráticos menos a suma dos non residuos no rango 1, 2, ... , q − 1 é un número negativo.

Por exemplo, módulo 11,

1, 2, 3, 4, 5, 6, 7, 8, 9, 10 (residuos en grosa)

1 + 4 + 9 + 5 + 3 = 22, 2 + 6 + 7 + 8 + 10 = 33, e a diferenza é −11.

Dirichlet tamén demostrou que para o primo q ≡ 3 (mod 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.$

Isto implica que hai máis residuos cadráticos que non residuos entre os números 1, 2,... , ( q − 1)/2.

Por exemplo, módulo 11 hai catro residuos inferiores a 6 (é dicir, 1, 3, 4 e 5), pero só un non residuo (o 2).

Todas as demostracións coñecidas destes dous teoremas dependen da análise; ninguén publicou nunca unha proba simple ou directa de ningunha das dúas afirmacións.

Lei da reciprocidade cadrática

Se p e q son primos impares, entón:

( (p é un residuo cadrático mod q) se e só se (q é un residuo cadrático mod p ) ) se e só se (polo menos un de p e q é congruente con 1 mod 4).

É dicir:

$\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.

Así, para os números a e os primos impares p que non dividen a, temos:

a	a é un residuo cadrático mod p se e só se	a	a é un residuo cadrático mod p se e só se
1	(todo p primo)	−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 p primo)	−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 p primo)	−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)

Atopar raíces cadradas módulo n

Aquí aparece unha diferenza importante entre os módulos primos e compostos. Módulo un primo $p$, un residuo cadrático $a$ ten cero raíces se $a\ N\ p$, unha se $a\equiv 0{\pmod {p}}$ ou dúas se $a\ R\ p$ e $\gcd(a,p)=1$.

En xeral, se escribimos un módulo composto $n$ na súa factorización en primos $p_{i}$, e hai $n_{1}$ raíces módulo $p_{1}$, $n_{2}$ módulo $p_{2}$, $n_{3}$ módulo $p_{3}$,... , haberá o produto $n_{1}$ $n_{2}$ $n_{3}$... raíces módulo $n$.

A forma teórica de combinar solucións módulo potencias primas para facer solucións módulo $n$ chámase teorema chinés do resto.

Por exemplo:

Solucionar x² ≡ 6 (mod 15).

x² ≡ 6 (mod 3) ten unha solución = 0; e por outra parte x² ≡ 6 (mod 5) ten dúas = 1 e 4.

e hai dúas solucións módulo 15, que son 6 e 9 (calculadas co teorema chinés do resto).

Solucionar x² ≡ 4 (mod 15).

x² ≡ 4 (mod 3) ten dúas solucións = 1 e 2; e por outra parte x² ≡ 4 (mod 5) ten outras dúas = 2 e 3.

e hai catro solucións módulo 15, é dicir, 2, 7, 8 e 13 (calculadas co teorema chinés do resto).

Solucionar x² ≡ 7 (mod 15).

x² ≡ 7 (mod 3) ten dúas solucións, 1 e 2; e despois temos x² ≡ 7 (mod 5) non ten solucións.

e por tanto non hai solucións módulo 15.

Módulo potencia de primo

Primeiro de todo, se o módulo $n$ é primo, o símbolo de Legendre $\left({\frac {a}{n}}\right)$ pódese calcular rapidamente usando unha variante do algoritmo de Euclides ou o criterio de Euler. Se é −1 non hai solución.

En segundo lugar, asumindo que $\left({\frac {a}{n}}\right)=1$, se $n\equiv 3{\pmod {4}}$, Lagrange descubriu que as solucións están dadas por

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

e Legendre atopou unha solución similar se $n\equiv 5{\pmod {8}}$:

$x\equiv {\begin{cases}\pm a^{(n+3)/8}{\pmod {n}}&{\text{ se }}a{\text{ é un residuo cuártico modulo }}n\\\pm a^{(n+3)/8}2^{(n-1)/4}{\pmod {n}}&{\text{ se }}a{\text{ é un non residuo cuártico modulo }}n\end{cases}}$

Para un primo de tipo $n\equiv 1{\pmod {8}}$, porén, non hai unha fórmula coñecida. Tonelli (en 1891) e Cipolla atoparon algoritmos eficientes que funcionan para tódolos módulos primos. Ambos os algoritmos requiren atopar un non residuo módulo $n$, e non hai un algoritmo determinista eficiente coñecido para facelo. Mais como a metade dos números entre 1 e $n$ son non residuos, escollemos números $x$ ao azar e calculando o símbolo de Legendre $\left({\frac {x}{n}}\right)$ ata que se atope un non residuo rapidamente. Unha pequena variante deste algoritmo é o algoritmo de Tonelli–Shanks .

Se o módulo $n$ é unha potencia de primo $n=p^{a}$, pódese atopar unha solución módulo $p$ e "elevarse" a unha solución módulo $n$ usando o lema de Hensel ou un algoritmo de Gauss.

Módulo composto

Se o módulo $n$ foi factorizado en potencias primas, a solución foi discutida anteriormente.

Se $n$ non é congruente con 2 módulo 4 e o símbolo de Kronecker $\left({\tfrac {a}{n}}\right)=-1$ daquela non hai solución. Se $n$ é congruente con 2 módulo 4 e $\left({\tfrac {a}{n/2}}\right)=-1$, daquela tampouco non hai solución. Se $n$ non é congruente con 2 módulo 4 e $\left({\tfrac {a}{n}}\right)=1$, ou $n$ é congruente con 2 módulo 4 e $\left({\tfrac {a}{n/2}}\right)=1$ pode haber ou non.

Se non se coñece a factorización completa de $n$, e $\left({\tfrac {a}{n}}\right)=1$ e $n$ non é congruente con 2 módulo 4, ou $n$ é congruente con 2 módulo 4 e $\left({\tfrac {a}{n/2}}\right)=1$, sábese que o problema é equivalente á factorización de $n$ (é dicir, unha solución eficiente a calquera dos problemas podería usarse para resolver o outro de forma eficiente).

O artigo congruencia de cadrados analiza como atopar dous números x e y onde x² ≡ y² (mod n) e x ≠ ±y é suficiente para factorizar n de forma eficiente.

Determinar se $a$ é un residuo cadrático ou non residuo módulo n pódese facer de forma eficiente para $n$ primo calculando o símbolo de Legendre. No entanto, para o composto $n$, isto forma o problema dos residuos cadráticos, asumíndose que é bastante difícil.

En xeral, para determinar se $a$ é un residuo cadrático módulo un n composto, pódese usar o seguinte teorema:

Sexa n > 1 e gcd(a,n) = 1. Entón x² ≡ a (mod n) ten solución se e só se:

• O símbolo de Legendre $\left({\tfrac {a}{p}}\right)=1$ para todos os divisores primos impares $p$ de $n$.
• a ≡ 1 (mod 4) se $n$ é divisíbel por 4 mais non por 8; ou a ≡ 1 (mod 8) se $n$ é divisíbel por 8.

Aplicacións dos residuos cadráticos

Acústica

Os difusores de son baseáronse nos conceptos de raíces módulo n e residuos cadráticos.

Teoría de grafos

Os grafos de Paley son grafos densos e non dirixidos, un por cada primo p ≡ 1 (mod 4), que forman unha familia infinita de grafos de conferencia, que dan lugar a unha familia infinita de matrices de conferencia simétricas.

Criptografía

O feito de que atopar unha raíz cadrada dun número módulo un composto $n$ moi grande é equivalente á factorización (o cal considérase un problema difícil), utilizouse para construír esquemas criptográficos como o sistema criptográfico Rabin e a transferencia incosciente. O problema dos residuos cadráticos é a base do sistema criptográfico Goldwasser-Micali .

Test de primalidade

O criterio de Euler é unha fórmula para calcular o símbolo de Legendre (a|p) onde $p$ é primo. Se $p$ é composto, a fórmula pode calcular correctamente (a|p) ou non. A proba de primalidade de Solovay-Strassen para determinar se un determinado número $n$ é primo ou composto elixe un $a$ aleatorio e calcula (a|n) usando unha modificación do algoritmo de Euclides, e tamén usando o criterio de Euler. Se os resultados discrepan, $n$ é composto; se coinciden, $n$ pode ser composto ou primo. Para un composto $n$ polo menos a metade dos valores de $a$ no intervalo 2, 3,... , n − 1 devolverá "$n$ é composto"; para un primo $n$ non devolve ningún. Se despois de usar moitos valores diferentes de $a$, $n$ non se demostrou composto, denomínase "primo probábel".

O test de primalidade de Miller-Rabin baséase nos mesmos principios. Hai unha versión determinista do mesmo, mais a proba de que funciona depende da hipótese xeneralizada de Riemann; a saída desta proba é "$n$ é definitivamente composto" ou "$n$ é primo ou a GRH é falsa".

Táboa de residuos cadráticos

A seguinte táboa (secuencia A096008 na OEIS) enumera os residuos cadráticos mod 1 a 75 (un número rubio significa que non é coprimo con $n$). (Para os residuos cadráticos coprimos con $n$, ver (secuencia A096103 na OEIS) e para os residuos cadráticos distintos de cero ver (secuencia A046071 na OEIS).)

n	residuos cadráticos mod n	n	residuos cadráticos mod n	n	residuos cadrá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

Residuos cadráticos (véxase tamén (secuencia A048152 na OEIS), (secuencia 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

Véxase tamén

Bibliografía

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

Outros artigos

• Criterio de Euler
• Lema de Gauss
• Lema de Zolotarev
• Suma de caracteres
• Lei da reciprocidade cadrática
• Símbolo de Jacobi
• Símbolo de Kronecker
• Carácter de Dirichlet

Ligazóns externas

• Weisstein, Eric W. "Quadratic Residue". MathWorld.