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:



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 Lemmemeyer, Ch. 1 e formaron conxecturas Lemmermeyer, pp 6–8, p. 16 ff 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,... , . Debido a que a2 ≡ (n − a)2 (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  residuos (incluíndo 0) e  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.Gauss, DA, art. 98

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

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 suplementoGauss, DA, art 111 á 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  é un número impar e  , daquela  é un residuo módulo  se e só se  ≡ 1 (mod 8). Gauss, DA, art. 103Por exemplo,  os cadrados dos impares son

 12 ≡ 152 ≡ 1
 32 ≡ 132 ≡ 9
 52 ≡ 112 ≡ 25
 72 ≡ 92 ≡ 49 ≡ 17

 e os cadrados dos pares son

 02 ≡ 82 ≡ 162 ≡ 0
 22 ≡ 62 ≡ 102 ≡ 14 2 ≡ 4
 42 ≡ 122 ≡ 16. Polo tanto, un número distinto de cero é un residuo , se e só se é da forma 4k (8 n + 1).

Un número  coprimo a un primo impar  é un residuo módulo calquera potencia de  se e só se é un residuo módulo .Gauss, DA, art. 101

Cando o módulo é n, temos que k
 é un residuo módulo n se k ≥ n
 é un non residuo módulo n  se k < n é impar
 é un residuo módulo n se k < n é par e  é un residuo
 é un non residuo módulo  n se k < n é par e  é un non residuo.Gauss, DA, art. 102

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  = k, os produtos de residuos e non residuos relativamente primos para  obedecen as mesmas regras que o visto para mod ;  é 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  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  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  pk 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 e.g.,  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 Gauss, DA, art. 131 utilizou as letras  e  para indicar residuos e non residuos, respectivamente;

 por exemplo,  e , ou  e .

Aínda que esta notación é compacta e conveniente para algúns propósitos,e.g. úsano Hardy e Wright Gauss, DA, art 230 ff. 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  e números primos impares positivos  como



Hai dúas razóns polas que se tratan especialmente os números ≡ 0 (mod ). 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  e os números complexos baixo multiplicación. Definindo  podemos estender o seu dominio ao semigrupo multiplicativo de todos os números enteiros.Esta extensión do dominio é necesaria para definir as funcións L.

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.Véxase :pt:Símbolo de Legendre#Propriedades do símbolo Legendre para  exemplos Tamén se pode xeneralizar facilmente a residuos dunha potencia maior.Lemmermeyer, pp 111-fin

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  o símbolo de Jacobi sería:



sendo  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  un enteiro distinto de 0, con factorización  onde . Sexa  un enteiro, o símbolo de Kronecker   sería:



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.. Estes son resultados clásicos. Sexa q un número primo, s unha variábel complexa e definimos unha función L de Dirichlet como



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



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),



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:



onde  é 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 , un residuo cadrático  ten cero raíces se , unha se  ou dúas se   e .

En xeral, se escribimos un módulo composto   na súa factorización en primos , e hai  raíces módulo ,  módulo ,  módulo ,... , haberá o produto    ... raíces módulo .

A forma teórica de combinar solucións módulo potencias primas para facer solucións módulo  chámase teorema chinés do resto. ; require O(log2m) pasos onde   é o número de primos que dividen  .

Por exemplo:

 Solucionar x2 ≡ 6 (mod 15).
 x2 ≡ 6 (mod 3) ten unha solución = 0; e por outra parte x2 ≡ 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 x2 ≡ 4 (mod 15).
 x2 ≡ 4 (mod 3) ten dúas solucións = 1 e 2; e por outra parte x2 ≡ 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 x2 ≡ 7 (mod 15).
 x2 ≡ 7 (mod 3) ten dúas solucións, 1 e 2; e despois temos x2 ≡ 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  é primo, o símbolo de Legendre  pódese calcular rapidamente usando unha variante do algoritmo de Euclides; computar  require O(log a log n) pasos ou o criterio de Euler. Se é −1 non hai solución. 

En segundo lugar, asumindo que , se , Lagrange descubriu que as solucións están dadas por



e Legendre atopou unha solución similar Lemmermeyer, p. 29 se :



Para un primo de tipo , porén, non hai unha fórmula coñecida. Tonelli ; the algorithm requires O(log4n) steps. (en 1891) e Cipolla ; o algoritmo require O(log3 n) pasos e non é determinístico. atoparon algoritmos eficientes que funcionan para tódolos módulos primos. Ambos os algoritmos requiren atopar un non residuo módulo , e non hai un algoritmo determinista eficiente coñecido para facelo. Mais como a metade dos números entre 1 e  son non residuos, escollemos  números  ao azar e calculando o símbolo de Legendre  ata que se atope un non residuo rapidamente. Unha pequena variante deste algoritmo é o algoritmo de Tonelli–Shanks .

Se o módulo  é unha potencia de primo , pódese atopar unha solución módulo  e "elevarse" a unha solución módulo  usando o lema de Hensel ou un algoritmo de Gauss.Gauss, DA, art. 101

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

Se  non é congruente con 2 módulo 4 e o símbolo de Kronecker  daquela non hai solución. Se  é congruente con 2 módulo 4 e , daquela tampouco non hai solución. Se  non é congruente con 2 módulo 4 e , ou  é congruente con 2 módulo 4 e  pode haber ou non.

Se non se coñece a factorización completa de , e  e  non é congruente con 2 módulo 4, ou  é congruente con 2 módulo 4 e , sábese que o problema é equivalente á factorización de  (é 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  e  é suficiente para factorizar n de forma eficiente.Crandall & Pomerance, ex. 6.5 & 6.6, p.273

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

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

Sexa  e . Entón  ten solución se e só se:

 O símbolo de Legendre  para todos os divisores primos impares  de .
  se  é divisíbel por 4 mais non por 8; ou  se  é 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  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  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  é primo. Se  é 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  é primo ou composto elixe un  aleatorio e calcula (a|n) usando unha modificación do algoritmo de Euclides,  e tamén usando o criterio de Euler. ; O criterio de Euler require O(log3 n) pasos Se os resultados discrepan,  é composto; se coinciden,  pode ser composto ou primo. Para un composto  polo menos a metade dos valores de  no intervalo 2, 3,... , n − 1 devolverá " é composto"; para un primo  non devolve ningún. Se despois de usar moitos valores diferentes de ,  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 é " é definitivamente composto" ou " é primo ou a GRH é falsa".

 Táboa de residuos cadráticos 
A seguinte táboa  enumera os residuos cadráticos mod 1 a 75 (un número rubio significa que non é coprimo con ). (Para os residuos cadráticos coprimos con , ver  e para os residuos cadráticos distintos de cero ver .)
nresiduos cadráticos mod nnresiduos cadráticos mod nnresiduos cadráticos mod n1026, 1, 3, , 9, , , , , , 17, , 23, 2551, 1, 4, , 13, , 16, , 19, , 25, , , , , , 43, 492, 127, 1, 4, 7, , 10, 13, 16, 19, 22, 2552, 1, , 9, , , , 17, 25, 29, , , , 493, 128, 1, , , 9, , , 2553, 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, 524, 129, 1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 2854, 1, , 7, , , 13, , 19, , 25, , , 31, , , 37, , 43, , 49, 5, 1, 430, 1, , , , , , , 19, , , 55, 1, 4, , 9, , 14, , 16, , , 26, 31, 34, 36, , , 496, 1, , 31, 1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 2856, 1, , , 9, , 25, , , , , 7, 1, 2, 432, 1, , 9, , 17, 2557, 1, 4, , 7, , 16, , , 25, 28, , , , , 43, , 49, , 558, 1, 33, 1, , 4, , , , 16, , 25, , 3158, 1, , 5, , 7, 9, 13, , , , 23, , 25, , , , 33, , 35, , , , 45, 49, 51, , 53, , 579, 1, 4, 734, 1, , , , 9, 13, 15, , , , 19, 21, 25, , , , 3359, 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, 5710, 1, , , , 935, 1, 4, 9, 11, , , 16, , , 29, 60, 1, , , , , , , , , , 4911, 1, 3, 4, 5, 936, 1, , , 13, , 25, 61, 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, 6012, 1, , 37, 1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 3662, 1, , , 5, 7, , 9, , , , , 19, , 25, , , , 33, 35, , , 39, , 41, 45, 47, 49, , 51, , 5913, 1, 3, 4, 9, 10, 1238, 1, , 5, , 7, 9, 11, , 17, , , 23, , 25, , , , 35, 63, 1, 4, , , 16, , 22, 25, , , 37, 43, 46, , 5814, 1, , , , , 9, 1139, 1, , 4, , 10, , , 16, 22, 25, , , 64, 1, , 9, , 17, 25, 33, , 41, 49, 5715, 1, 4, , , 40, 1, , 9, , , , , 65, 1, 4, 9, , 14, 16, , , 29, , , 36, , , 49, 51, , 56, 61, 6416, 1, , 941, 1, 2, 4, 5, 8, 9, 10, 16, 18, 20, 21, 23, 25, 31, 32, 33, 36, 37, 39, 4066, 1, , , , , , , , 25, , 31, , , , 37, , , , 49, , , , 17, 1, 2, 4, 8, 9, 13, 15, 1642, 1, , , , , , , , , 25, , , , 37, 67, 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, 6518, 1, , 7, , , 13, 43, 1, 4, 6, 9, 10, 11, 13, 14, 15, 16, 17, 21, 23, 24, 25, 31, 35, 36, 38, 40, 4168, 1, , , 9, 13, , , 21, 25, , 33, , 49, , 53, , 19, 1, 4, 5, 6, 7, 9, 11, 16, 1744, 1, , 5, 9, , , , 25, , , 3769, 1, , 4, , , , 13, 16, , , 25, , 31, , , , , 49, 52, , 55, 58, 6420, 1, , , 9, 45, 1, 4, , , 16, 19, , 31, 34, , 70, 1, , 9, 11, , , , , , 29, , , , 39, , , , , 51, , , , 21, 1, 4, , , , 16, 46, 1, , 3, , , , 9, , 13, , , , , 25, , 27, 29, 31, , 35, , 39, 4171, 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, 6422, 1, 3, , 5, 9, , , , 15, , 47, 1, 2, 3, 4, 6, 7, 8, 9, 12, 14, 16, 17, 18, 21, 24, 25, 27, 28, 32, 34, 36, 37, 4272, 1, , , , 25, , , , 49, , 23, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 1848, 1, , , , 25, , 73, 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, 7224, 1, , , , 49, 1, 2, 4, 8, 9, 11, 15, 16, 18, 22, 23, 25, 29, 30, 32, 36, 37, 39, 43, 44, 4674, 1, 3, , 7, 9, , 11, , , 21, 25, , 27, , , 33, , , , , , 41, , , 47, , 49, 53, , , 63, , 65, 67, , 71, 7325, 1, 4, 6, 9, 11, 14, 16, 19, 21, 2450, 1, , , 9, 11, , , 19, 21, , , , 29, 31, , , 39, 41, , , 4975, 1, 4, , , 16, 19, , , , 31, 34, , , 46, 49, , , 61, 64, , 
+Residuos cadráticos (véxase tamén , )x12345678910111213141516171819202122232425x2149162536496481100121144169196225256289324361400441484529576625mod 10000000000000000000000000mod 21010101010101010101010101mod 31101101101101101101101101mod 41010101010101010101010101mod 51441014410144101441014410mod 61434101434101434101434101mod 71422410142241014224101422mod 81410141014101410141014101mod 91407704101407704101407704mod 101496569410149656941014965mod 111495335941014953359410149mod 121494101494101494101494101mod 13149312101012394101493121010123941mod 1414921187811294101492118781129mod 1514911064461019410149110644610mod 161490941014909410149094101mod 171491682151313152816941014916821513mod 18149167013109101307169410149167013mod 19149166171175571117616941014916617mod 20149165169410149165169410149165mod 211491641571181616181715416941014916mod 22149163145201512111215205143169410149mod 23149162133181286681218313216941014mod 241491611211694101491611211694101mod 251491601124146021191921061424110169410

 Notas 

 Véxase tamén 

 Bibliografía 

 A7.1: AN1, pg.249.

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 

Categoría:Teoría de números
Categoría:Wikipedia:Páxinas con traducións non revisadas