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(\mathrm{mod}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,... , Modelo:Nowrap. 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 Modelo:Math residuos (incluíndo 0) e Modelo:Math 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 Modelo:Mvar é un número impar e Modelo:Math, daquela Modelo:Mvar é un residuo módulo Modelo:Mvar se e só se Modelo:Mvar ≡ 1 (mod 8).

Por exemplo, Modelo:Math 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 Modelo:Math, se e só se é da forma 4^k (8 n + 1).

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

Cando o módulo é Modelo:Mvarⁿ, temos que Modelo:Mvar^kModelo:Mvar

é un residuo módulo Modelo:Mvarⁿ se k ≥ n

é un non residuo módulo Modelo:Mvarⁿ se k < n é impar

é un residuo módulo Modelo:Mvarⁿ se k < n é par e Modelo:Mvar é un residuo

é un non residuo módulo Modelo:Mvarⁿ se k < n é par e Modelo:Mvar é 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 Modelo:Mvar = Modelo:Mvar^k, os produtos de residuos e non residuos relativamente primos para Modelo:Mvar obedecen as mesmas regras que o visto para mod Modelo:Mvar; Modelo:Mvar é 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 Modelo:Mvar 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 Modelo:Math e Modelo:Math para indicar residuos e non residuos, respectivamente;

por exemplo, Modelo:Math e Modelo:Math, ou Modelo:Math e Modelo:Math.

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 Modelo:Mvar e números primos impares positivos Modelo:Mvar 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{ non divide }a\\ -1& \text{se }a\mathrm{N}p\text{ e }p\text{ non divide }a\end{array}$

Hai dúas razóns polas que se tratan especialmente os números ≡ 0 (mod Modelo:Mvar). 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 módulo n|grupo multiplicativo de enteiros distintos de cero módulo Modelo:Mvar]] e os números complexos baixo multiplicación. Definindo $(\frac{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 $\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}^{\mathrm{\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 }{(2-\left(\frac{2}{q}\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 $aNp$, unha se $a\equiv 0(\mathrm{mod}p)$ ou dúas se $aRp$ 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(\mathrm{mod}4)$, Lagrange descubriu que as solucións están dadas por

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

e Legendre atopou unha solución similar se $n\equiv 5(\mathrm{mod}8)$:

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

Para un primo de tipo $n\equiv 1(\mathrm{mod}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(\frac{a}{n}\right)=-1$ daquela non hai solución. Se $n$ é congruente con 2 módulo 4 e $\left(\frac{a}{n/2}\right)=-1$, daquela tampouco non hai solución. Se $n$ non é congruente con 2 módulo 4 e $\left(\frac{a}{n}\right)=1$, ou $n$ é congruente con 2 módulo 4 e $\left(\frac{a}{n/2}\right)=1$ pode haber ou non.

Se non se coñece a factorización completa de $n$, e $\left(\frac{a}{n}\right)=1$ e $n$ non é congruente con 2 módulo 4, ou $n$ é congruente con 2 módulo 4 e $\left(\frac{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 Modelo:Math e Modelo:Math é 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 Modelo:Math e Modelo:Math. Entón Modelo:Math ten solución se e só se:

• O símbolo de Legendre $\left(\frac{a}{p}\right)=1$ para todos os divisores primos impares $p$ de $n$.
• Modelo:Math se $n$ é divisíbel por 4 mais non por 8; ou Modelo:Math 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 Modelo:Mvar 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 Modelo: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 Modelo:OEIS e para os residuos cadráticos distintos de cero ver Modelo:OEIS.)

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

Residuos cadráticos (véxase tamén Modelo:OEIS, Modelo: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

• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro A7.1: AN1, pg.249.
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro

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

• Modelo:MathWorld