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
editarFermat, Euler, Lagrange, Legendre e outros teóricos dos números dos séculos XVII e XVIII xa estableceron teoremas [1] e formaron conxecturas [2] 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 a2 ≡ (n − a)2 (mod n ), a lista de cadrados módulo n é simétrica arredor de n /2. Isto pódese ver na táboa de abaixo.
Módulo un número primo
editarMó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. [3]
Sen o 0, módulo un número primo impar hai un número igual de residuos e non residuos. [4]
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 [5] á lei da reciprocidade cuadrática é que se p ≡ 1 (mod 4) entón −1 é un residuo cuadrá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
editarTodos os cadrados dos impares son ≡ 1 (mod 8) e, polo tanto, tamén ≡ 1 (mod 4). Se a é un número impar e m = 2n, n > 2, daquela a é un residuo módulo m se e só se a ≡ 1 (mod 8). [6]
Por exemplo, mod (32=25) 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 mod 2n, n > 2, se e só se é da forma 4k (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. [7]
Cando o módulo é pn, temos que pka
- é un residuo módulo pn se k ≥ n
- é un non residuo módulo pn se k < n é impar
- é un residuo módulo pn se k < n é par e a é un residuo
- é un non residuo módulo pn se k < n é par e a é un non residuo. [8]
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 = pk, 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
editarNeste 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 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 [9] 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
editarGauss [10] utilizou 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, [11] [12] 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
Hai dúas razóns polas que os números ≡ 0 (mod p) trátanse especialmente. 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 números enteiros distintos de cero módulo p e os números complexos baixo multiplicación. Definindo podemos estender o seu dominio ao semigrupo multiplicativo de todos os números enteiros. [13]
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. [14] Tamén se pode xeneralizar facilmente a residuos dunha potencia maior. [15]
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
editarExisten 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. [16] Sexa q un número primo, s unha variable 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 cuadráticos que non residuos entre os números 1, 2,... , ( q − 1)/2.
Por exemplo, no 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. [17]
Lei da reciprocidade cuadrática
editarSe p e q son primos impares, entón:
( (p é un residuo cuadrático mod q) se e só se (q é un residuo cuadrá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 cuadrático mod p se e só se | a | a é un residuo cuadrá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
editarAquí 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 ≡ 0 (mod p) ou dúas se a R p e mcd(a, p) = 1.
En xeral, se escribimos un módulo composto n na súa factorización en primos , e hai raíces módulo , módulo , módulo ,... , haberá o produto ... 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. [18]
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 de potencia de primo
editarPrimeiro de todo, se o módulo n é primo, o símbolo de Legendre pódese calcular rapidamente usando unha variante do algoritmo de Euclides [19] ou o criterio de Euler . Se é −1 non hai solución. En segundo lugar, asumindo que , se n ≡ 3 (mod 4), Lagrange descubriu que as solucións están dadas por
e Legendre atopou unha solución similar [20] se n ≡ 5 (mod 8):
Para un primo de tipo n ≡ 1 (mod 8), porén, non hai unha fórmula coñecida. Tonelli [21] (en 1891) e Cipolla [22] atoparon algoritmos eficientes que funcionan para tódolos módulos primos. Ambos 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 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 e, 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. [7]
Módulo composto
editarSe 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 daquela non hai solución. Se n é congruente con 2 módulo 4 e , daquela tampouco non hai solución. Se n non é congruente con 2 módulo 4 e , ou n é congruente con 2 módulo 4 e , pode haber ou non.
Se non se coñece a factorización completa de n, e e n non é congruente con 2 módulo 4, ou n é congruente con 2 módulo 4 e , 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 x2 ≡ y2 (mod n) e x ≠ ±y é suficiente para factorizar n de forma eficiente. [23]
Determinar se a é un residuo cuadrático ou non residuo módulo n pódese facer de forma eficiente para n primo calculando o símbolo de Legendre. Non obstante, para o composto n, isto forma o problema dos residuos cuadrático, asumíndose que é bastante difícil.
En xeral, para determinar se a é un residuo cuadrático módulo un n composto, pódese usar o seguinte teorema: [24]
Sexa n > 1 e gcd(a,n) = 1 . Entón x2 ≡ a (mod n) ten solución se e só se:
- O símbolo Legendre para todos os divisores primos impares p de n .
- a ≡ 1 (mod 4) se n é divisible por 4 mais non por 8; ou a ≡ 1 (mod 8) se n é divisible por 8.
Aplicacións dos residuos cadráticos
editarAcústica
editarOs difusores de son baseáronse nos conceptos de raíces módulo n e residuos cadráticos. [25]
Teoría de grafos
editarOs 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
editarO 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 cuadráticos é a base do sistema criptográfico Goldwasser-Micali .
Test de primalidade
editarO 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, [26] e tamén usando o criterio de Euler. [27] 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 probable".
O test de primalidade de Miller-Rabin baséase nos mesmos principios. Hai unha versión determinista do mesmo, pero 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
editarA 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 OEIS : A096103, e para os residuos cadráticos distintos de cero, ver (secuencia A046071 na OEIS).)
n | residuos cadráticos mod n | n | residuos cadráticoss 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 |
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 |
Notas
editar- ↑ Lemmemeyer, Ch. 1
- ↑ Lemmermeyer, pp 6–8, p. 16 ff
- ↑ Gauss, DA, art. 98
- ↑ Gauss, DA, art. 96
- ↑ Gauss, DA, art 111
- ↑ Gauss, DA, art. 103
- ↑ 7,0 7,1 Gauss, DA, art. 101
- ↑ Gauss, DA, art. 102
- ↑ e.g., Ireland & Rosen 1990, p. 50
- ↑ Gauss, DA, art. 131
- ↑ e.g. Hardy and Wright use it
- ↑ Gauss, DA, art 230 ff.
- ↑ This extension of the domain is necessary for defining L functions.
- ↑ Véxase Legendre symbol#Properties of the Legendre symbol para exemplos
- ↑ Lemmermeyer, pp 111–end
- ↑ Davenport 2000, p. 8–9, 43–51. These are classical results.
- ↑ Davenport 2000, p. 9
- ↑ Bach & Shallit 1996, p. 104 ff; it requires O(log2 m) steps where m is the number of primes dividing n.
- ↑ Bach & Shallit 1996, p. 113; computing requires O(log a log n) steps
- ↑ Lemmermeyer, p. 29
- ↑ Bach & Shallit 1996, p. 156 ff; the algorithm requires O(log4n) steps.
- ↑ Bach & Shallit 1996, p. 156 ff; o algoritmo require O(log3 n) pasos e non é determinístico.
- ↑ Crandall & Pomerance, ex. 6.5 & 6.6, p.273
- ↑ . 2007. p. 195. Falta o
|title=
(Axuda) - ↑ (PDF) http://downloads.bbc.co.uk/rd/pubs/reports/1990-15.pdf. Falta o
|title=
(Axuda) - ↑ Bach & Shallit 1996, p. 113
- ↑ Bach & Shallit 1996, p. 109–110; Euler's criterion requires O(log3 n) steps
Véxase tamén
editarBibliografía
editar- 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
editar- 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