Don't take life too seriously: it's just a temporary situation

Residui quadratici

Teoria dei numeri 

Indice

  1. 1. Pagina principale
  2. 2. Distribuzione dei residui quadratici

Sono chiamati “residui quadratici modulo p” i numeri n per i quali esiste un intero x tale che x2n mod p. Per esempio, 4 è residuo quadratico modulo 5, perché 32 ≡ 4 mod 5.

Sono intensamente studiati da quasi tre secoli, ma il nome fu proposto da Shanks solo nel 1962.

 

Strettamente legato ai residui quadratici è il simbolo di Legendre Simbolo di Legendre (n | p); è definito solo se p è primo e vale 0, se n è un multiplo di p, 1 se n è un residuo quadratico modulo p, –1 altrimenti.

 

Per trovare tutti i residui quadratici modulo n basta calcolare i quadrati degli interi da 1 a Massimo intero non superiore a n / 2 modulo n, perché a2 ≡ (na)2 mod 2, quindi i quadrati sono simmetrici rispetto alla metà di n. Per esempio, la sequenza dei quadrati da 1 a 12 modulo 13 è: 1, 4, 9, 3, 12, 10, 10, 12, 3, 9, 4, 1.

 

La tabella seguente mostra i residui quadratici modulo gli interi da 2 a 20.

n

Residui quadratici modulo n

2

1

3

1

4

1, 3

5

1, 4

6

1, 5

7

1, 2, 4

8

1, 7

9

1, 2, 4, 5, 7, 8

10

1, 3, 9

11

1, 3, 4, 5, 9

12

1, 7

13

1, 3, 4, 9, 10, 12

14

1, 3, 5, 9, 13

15

1, 2, 4, 8

16

1, 3, 5, 7, 9, 11, 13, 15

17

1, 2, 4, 8, 9, 13, 15, 16

18

1, 7, 17

19

1, 4, 5, 6, 7, 9, 11, 16, 17

20

1, 9, 11, 19

 

Alcune proprietà dei residui quadratici:

  • un intero è residuo quadratico modulo una potenza di un primo dispari p se e solo se è residuo quadratico modulo p;

  • se un intero è residuo quadratico modulo n, è residulo modulo le potenze pk di ogni primo p che divide n;

  • se un intero è nonresiduo quadratico modulo n, è nonresiduo modulo le potenze pk di almeno un primo p che divide n;

  • l’inverso moltiplicativo di un residuo quadratico modulo n, se esiste, è un residuo quadratico modulo n;

  • l’inverso moltiplicativo di un nonresiduo quadratico modulo n, se esiste, è un nonresiduo quadratico modulo n;

  • il prodotto di due residui quadratici modulo n è un residuo quadratico modulo n.

  • il prodotto di due nonresidui quadratici modulo una potenza pk di un primo dispari (incluso p stesso) è un residuo quadratico modulo pk;

  • il prodotto di un residuo quadratico e un nonresiduo quadratico modulo una potenza pk di un primo dispari (incluso p stesso) è un nonresiduo quadratico modulo pk;

  • se p è un primo della forma 4k + 1, –n è un residuo quadratico modulo p se e solo se lo è n;

  • se p è un primo della forma 4k + 3, –n è un residuo quadratico modulo p se e solo se non lo è n;

  • se p è un primo della forma 4n + 1, tutti i divisori dispari di n sono residui quadratici modulo p;

  • una potenza è un residuo quadratico modulo un numero che non sia un suo divisore se e solo se l’esponente è pari, quindi per esempio, 33 = 27 non è residuo quadratico modulo nessun numero, a parte 3.

 

Dato un primo p dispari, definiamo S come l’insieme degli interi da 1 a (p – 1) / 2; moltiplichiamo tutti gli interi di S per x: x è un residuo quadratico modulo p se e solo se il numero di quelli non congruenti a un elemento di S modulo p è pari (lemma di Gauss). Per esempio, nel caso di 13, S = { 1, 2, 3, 4, 5, 6 }; moltiplicando gli elementi per x = 7 otteniamo { 7, 14, 21, 28, 35, 42 }, ossia, prendendo i prodotti modulo 13, { 7, 1, 8, 2, 9, 3 }; tra questi ce ne sono 3 non in S (7, 8 e 9) e 7 non è un residuo quadratico modulo 13. Nel caso di 4 invece i prodotti modulo 13 sono { 4, 8, 12, 3, 7, 11 } e tra questi ce ne sono 4 non in S (8, 12, 7 e 11) e 4 è un residuo quadratico modulo 13.

 

La legge di reciprocità quadratica afferma che:

  • dati due primi p e q, almeno uno dei quali della forma 4k + 1, p è residuo quadratico modulo q se e solo se q è residuo quadratico modulo p;

  • dati due primi p e q, entrambi della forma 4k + 3, p è residuo quadratico modulo q se e solo se q è nonresiduo quadratico modulo p.

 

Eulero dimostrò che se p è un primo dispari, Formula del teorema di Eulero sui residui quadratici per ogni 0 < b < p. Sfortunatamente non è vero l’inverso: se la relazione vale per un intero dispari p e un intero b, col simbolo di Jacobi al posto del simbolo di Legendre, p non è necessariamente primo (v. pseudoprimi di Eulero – Jacobi). E’ un peccato, perché il simbolo di Jacobi si può calcolare facilmente anche senza conoscere la scomposizione in fattori primi di p, quindi questo sarebbe un buon metodo per decidere se un intero è primo o no.

 

Sfruttando il teorema di Eulero è semplice determinare se un numero è un residuo quadratico modulo un primo fissato; in alcuni casi si possono anche determinare facilmente a priori tutti i primi modulo i quali un intero è residuo quadratico:

  • 1 è residuo quadratico modulo tutti i primi;

  • –1 è residuo quadratico modulo 2 e tutti e soli i primi della forma 4n + 1;

  • 2 è residuo quadratico modulo tutti e soli i primi della forma 8n + 1 e 8n + 7;

  • –2 è residuo quadratico modulo tutti e soli i primi della forma 8n + 1 e 8n + 3;

  • 3 è residuo quadratico modulo tutti e soli i primi della forma 12n + 1 e 12n + 11;

  • –3 è residuo quadratico modulo tutti e soli i primi della forma 6n + 1;

  • 5 è residuo quadratico modulo tutti e soli i primi della forma 5n + 1 e 5n + 4;

  • –5 è residuo quadratico modulo tutti e soli i primi della forma 20n + 1, 20n + 3, 20n + 7, e 20n + 9;

  • 6 è residuo quadratico modulo tutti e soli i primi della forma 24n + 1, 24n + 5, 24n + 19 e 24n + 23;

  • –6 è residuo quadratico modulo tutti e soli i primi della forma 24n + 1, 24n + 5, 24n + 7, e 24n + 11.

Alcuni di questi risultati possono essere espressi in una forma più compatta usando il simbolo di Lagrange, per p primo dispari: Valore del simbolo di Lagrange (1 | p), Valore del simbolo di Lagrange (–1 | p), Valore del simbolo di Lagrange (2 | p), Valore del simbolo di Lagrange (–2 | p).

 

I primi modulo i quali m è residuo quadratico sono tutti e soli quelli della forma mn + k, per un valore di n dipendente da m e alcuni valori di k.

 

Un intero maggiore di zero è residuo quadratico modulo una potenza di 2 maggiore di 4 se e solo se è della forma 4m(8k + 1).

 

Il numero di residui quadratici quadrati modulo n, incluso zero, è una funzione moltiplicativa, e in particolare vale:

  • Numero di residui quadratici modulo una potenza di 2 con esponente pari, se n = 2q è una potenza di 2 con esponente pari;

  • Numero di residui quadratici modulo una potenza di 2 con esponente dispari, se n = 2q è una potenza di 2 con esponente dispari;

  • Numero di residui quadratici modulo un primo dispari, se n è un primo dispari;

  • Numero di residui quadratici modulo il quadrato di un primo dispari, se n = p2 è il quadrato di un primo dispari;

  • Numero di residui quadratici modulo una potenza di un primo dispari con esponente pari e maggiore di 2, se n = pq è una potenza di un primo dispari con esponente pari e maggiore di 2;

  • Numero di residui quadratici modulo una potenza di un primo dispari con esponente dispari e maggiore di 2, se n = pq è una potenza di un primo dispari con esponente dispari e maggiore di 2.

 

A. Gica dimostrò nel 2006 che:

  • gli unici primi modulo i quali non esista un residuo quadratico che sia un primo della forma 3k + 1 sono: 2, 3, 5, 7, 11 e 13;

  • gli unici primi modulo i quali non esista un residuo quadratico che sia un primo della forma 3k + 2 sono: 2, 3, 5 e 13;

  • gli unici primi modulo i quali non esista un residuo quadratico che sia un primo della forma 4k + 1 sono: 2, 3, 5, 7, 13 e 37.

  • gli unici primi modulo i quali non esista un residuo quadratico che sia un primo della forma 4k + 3 sono: 2, 3, 5, 7 e 17.

Gica avanzò anche la congettura che per ogni coppia di interi a e b primi tra loro vi sia un numero finito di primi, modulo i quali non esista un residuo quadratico che sia un primo della forma ak + b.

 

Se p è un primo della forma 4k + 3, la somma dei residui quadratici modulo p tra 1 e p è minore della somma dei nonresidui quadratici modulo p nello stesso intervallo, come dimostrò Peter Gustav Lejeune Dirichlet (Düren, allora Impero francese, oggi Germania, 13/2/1805 – Göttingen, Germania, 5/5/1859). Per esempio, nel caso di 11 i residui tra 1 e 10 sono 1, 3, 4, 5 e 9 e la loro somma è 22, mentre i non residui sono 2, 6, 7, 8 e 10 e la loro somma è 33.

Dirichlet dimostrò anche che se p è un primo della forma 4k + 3, vi sono più residui che nonresidui modulo p tra i numeri da 1 a (p – 1) / 2.

 

Se p è un primo maggiore di 3, la somma dei suoi residui quadratici e la somma dei suoi nonresidui quadratici sono multipli di p.

 

Se p è un primo maggiore di 5, la somma dei quadrati dei residui quadratici modulo p e la somma dei quadrati dei suoi nonresidui quadratici modulo p sono multipli di p.

 

Sapendo che m è un residuo quadratico modulo n diverso da zero, resta il problema di trovare le soluzioni dell’equazione x2m mod n; le soluzioni minori di n sono MCD(2r, φ(n)), dove r è il numero di fattori primi di n, quindi 2, se n è primo.

Il metodo per trovare le soluzioni dipende dal valore di n.

  • Se n è un primo della forma 4k + 3, le soluzioni sono ±mk + 1 mod n (Lagrange); per esempio, per n = 19 e m = 11, le soluzioni sono ±114 + 1 mod 19 = ±7.

  • Se n è un primo della forma 8k + 5 e q2k + 1 ≡ 1 mod n, le soluzioni sono ±mk + 1 mod n (Legendre); per esempio, per n = 29 e m = 7, le soluzioni sono ±73 + 1 mod 29 = ±6.

  • Se n è un primo della forma 8k + 5 e q2k + 1 ≡ –1 mod n, le soluzioni sono Soluzioni dell'equazione (Legendre); per esempio, per n = 29 e m = 9, le soluzioni sono Soluzioni dell'equazione per n = 29 e m = 9.

  • Se n è un primo della forma 4k + 1 non si conoscono formule altrettanto semplici, ma si conoscono algoritmi efficienti ideati da Alberto Tonelli nel 1891, successivamente migliorato da Daniel Shanks nel 1973, e Michele Cipolla (Palermo, 28/10/1880 – Palermo, 7/9/1947) nel 1897.

  • Se n è una potenza pr di un primo dispari p, si trova una soluzione modulo p, e da questa si ottiene la soluzione desiderata tramite il lemma di Hensel o un algoritmo di Gauss.

  • Se n è ha 2 o più fattori primi diversi, si trovano le soluzioni modulo i fattori primi, elevati alla potenza corretta, poi si combinano in tutti i modi possibili tramite il teorema dei resti cinese per ottenere le soluzioni modulo n.

Gli algoritmi per trovare le soluzioni presuppongono la conoscenza di un nonresiduo quadratico di n, ma trovarne uno non richiede troppo tempo, perché, supponendo vera una forma estesa dell’ipotesi di Riemann, è stato dimostrato che il minimo nonresiduo quadratico modulo un primo p è minore di 2log2p.

 

Zhi-Wei Sun avanzò alcune congetture sui residui quadratici di alcune forme particolari:

  • per n > 4 esiste un numero di Fibonacci minore di n / 2 che non è residuo quadratico modulo n;

  • per n > 2 esiste un numero di Lucas (I) minore di n che non è residuo quadratico modulo n;

  • per ogni primo p maggiore di 5 esiste un primo q minore di p, tale 2q + 1 non sia residuo quadratico modulo p.

Bibliografia

  • Adler, Andrew;  Coury, John E.;  The Theory of Numbers: a Text and Source Book of Problems, Londra, Jones and Bartlett Publishers, 1995.
  • Bressoud, David M.;  Factorization and Primality Testing, New York, Springer – Verlag, 1989.
  • Roberts, Joe;  The Lure of the Integers, The Mathematical Association of America, 1992 -

    Una miniera di informazioni sugli interi.

  • Wells, David;  Prime Numbers, John Wiley & Sons, 2005 -

    Una miniera di informazioni sui numeri primi.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.