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,... , . Debido a que *a*2 ≡ (*n* &#x2212; *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.

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

: 12 &#x2261; 152 &#x2261; 1
: 32 &#x2261; 132 &#x2261; 9
: 52 &#x2261; 112 &#x2261; 25
: 72 &#x2261; 92 &#x2261; 49 &#x2261; 17

 e os cadrados dos pares son

: 02 &#x2261; 82 &#x2261; 162 &#x2261; 0
: 22 &#x2261; 62 &#x2261; 102 &#x2261; 14 2 &#x2261; 4
: 42 &#x2261; 122 &#x2261; 16.
 Polo tanto, un número distinto de cero é un residuo , se e só se é da forma 4*k* (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 .

Cando o módulo é *n*, temos que *k*
:: é un residuo módulo *n* se *k* &#x2265; *n*
:: é un non residuo módulo *n*  se *k* &#x3C; *n* é impar
:: é un residuo módulo *n* se *k* &#x3C; *n* é par e  é un residuo
:: é un non residuo módulo  *n* se *k* &#x3C; *n* é par e  é 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  = *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 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  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, 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

: 
\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 ). 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 (\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=\pm1. 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* &#x2212; 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 é &#x2212;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* &#x2212; 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:

## 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 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 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  e  é 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  e . Entó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.
*  se n é divisíbel por 4 mais non por 8; ou  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  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* &#x2212; 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  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  e para os residuos cadráticos distintos de cero ver .)

## 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 
*