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