Note sulla teoria dei residui quadratici

Note sulla teoria dei residui quadratici

Roberto Volpe

di (*)

Versione MM01 – 6 giugno 2004

(*) Vercellese cultore della matematica

Questa nota è a disposizione di chiunque a patto che non se ne faccia commercio e che non venga modificata in alcun modo. Se volete segnalarmi errori o più semplicemente farmi sapere i vostri commenti potete inviarli all’indirizzo mistralrv@infinito.it.

R. Volpe – Note sulla teoria dei residui quadratici Versione MM01-6 giugno 2004

Indice

1. Introduzione......................................................................................................... 5

2. Residui quadratici modulo un numero primo ....................................................... 6

3. Il simbolo di Legendre e il criterio di Eulero. ........................................................ 7

4. La legge di reciprocità quadratica (LRQ)............................................................. 9

5. Congettura di Eulero e dimostrazione alternativa della LRQ. ............................. 12

6. Il calcolo del simbolo di Legendre e il simbolo di Jacobi..................................... 17

7. Residui quadratici modulo un numero intero. .................................................... 20

2 + + ≡

8. La congruenza quadratica .......................................... 27

mod

aX bX c 0 ( n)

9. Interi somma di due quadrati............................................................................. 31

( )

ℤ

10. Anello degli interi di Gauss i ......................................................................... 36

ℤ

2 2 2

+ =

11. L’equazione diofantea X Y cZ in ......................................................... 43

ℤ

2 2 l

+ =

12. L’equazione diofantea in .......................................................... 46

X Y Z ℤ

2 2 2 2

+ + =

13. L’equazione diofantea in ................................................. 49

X Y Z W

Bibliografia .................................................................................................................. 51

Pagina 3 di 51

R. Volpe – Note sulla teoria dei residui quadratici Versione MM01-6 giugno 2004

Pagina 4 di 51

R. Volpe – Note sulla teoria dei residui quadratici Versione MM01-6 giugno 2004

Introduzione

1. Introduzione. + +

“Se p è un numero primo della forma 4

n 1 , p sarà un residuo o non residuo di un qualsiasi numero primo che preso positivamente è un residuo o un non residuo di p . Se p è della forma

−

+

4

n 3 , p avrà la stessa proprietà.”

Carl Friedrich Gauss DISQUISITIONES ARITHMETICAE - Articolo 131

La legge della reciprocità quadratica fu congetturata e parzialmente dimostrata da Eulero e da Legendre, Gauss chiamava tale legge nella formulazione sopra riportata “Theorema Fundamentale”, e fu il primo a darne una dimostrazione soddisfacente evidenziando l’equivalenza con le formulazioni di Eulero e Legendre.

Queste note non hanno la pretesa di dire nulla di nuovo sull’argomento, ma sono semplicemente degli appunti di studio dell’autore. In teoria un lettore interessato al termine della lettura di queste note dovrebbe avere una panoramica generale di tutta la teoria sottesa dalla soluzione generale della congruenza:

2 + + ≡

aX bX c n

0 (mod )

Mi è sembrato naturale aggiungere anche il famoso teorema di Fermat sugli interi somma di due quadrati e i suoi ampliamenti, in quanto derivabili dalla teoria dei residui quadratici, e conseguentemente parlare degli interi di Gauss dandone una applicazione alla risoluzione della equazione diofantea:

2 2 2

+ =

X Y cZ

della equazione diofantea:

l

2 2

+ =

X Y Z

e infine della equazione diofantea:

2 2 2 2

+ + =

X Y Z W

ottenendo così una formula per le quadruple pitagoriche.

Analizzando queste equazioni diofantee si generalizza in tre direzioni differenti quanto noto sulle terne pitagoriche, e infatti in tutti e tre i casi le ritroveremo come caso particolare.

Sarebbe naturale proseguire parlando della teoria delle forme quadratiche binarie e ternarie a coefficienti interi e quindi parlare della equazione diofantea:

2 2 2

+ =

aX bY cZ

nota in letteratura come equazione di Legendre. Per ora non sono stati aggiunti questi argomenti alla presente nota, preferendo limitare la trattazione ad un breve cenno per quanto strettamente necessario a spiegare la dimostrazione di Legendre delle legge della reciprocità quadratica.

Si assumono come noti alcuni concetti base di teoria di numeri e di algebra, e per essi si può fare riferimento ai testi [A] e [MA] indicati in Bibliografia o alla vastissima bibliografia presente on-line.

Pagina 5 di 51

R. Volpe – Note sulla teoria dei residui quadratici Versione MM01-6 giugno 2004

Residui quadratici modulo un numero primo

2. Residui quadratici modulo un numero primo

2 ≡

Iniziamo con l’occuparci della risolubilità della congruenza con p primo dispari.

X a p

(mod )

Definizione 2.1

Sia p un primo dispari ed a un intero non divisibile per p. Diciamo che a è un residuo quadratico di p quando la

2 ≡

X a p

ha almeno una soluzione, altrimenti a è un residuo non quadratico.

(mod )

Osservazione 2.2

2 ≡

Per ogni intero a non divisibile per 2 (cioè ogni intero dispari) la congruenza ha

X a (mod 2

)

soluzioni, infatti il quadrato di un qualsiasi numero dispari è dispari e quindi congruo modulo 2 ad a. Il numero primo 2 costituisce una eccezione rispetto agli altri numeri primi perché possiede una sola classe di soluzioni tra loro tutte congrue modulo 2. Per gli altri primi invece esistono sempre due classi di soluzioni non congrue come dimostrato nella proposizione seguente.

Questo giustifica il fatto che 2 non sia contemplato nella definizione 2.1. In ogni caso vedremo

e ≥

e 2 con e 3, è necessaria una trattazione dettagliata.

meglio nel paragrafo 7 che per le potenze di 2, come 4

Proposizione 2.3

2 ≡

X a p

Se a è un residuo quadratico del numero primo dispari p, allora la congruenza (mod )

2

= ± ≡

b a p

ha esattamente due soluzioni non congruenti modulo p date da X b con.

(mod )

Dimostrazione

2 −

≡

Se allora b e b sono soluzioni e sono incongruenti modulo p. Infatti se per

b a p

(mod ) 2

= ≡

assurdo p | 2

b allora siccome MCD (

2

, p ) 1, segue che p | b da cui essendo b a p

(mod )

segue che p | a in contraddizione con la definizione 3.1.1. Se c è una soluzione di

2 2 2 2 2 2 2 2

− = − + − −

≡ − p c b

X a p p c a

allora ed essendo c a c b b a segue che, cioè

(mod ) | |

− + ≡ ≡ −

risulta che p | c b oppure p | c b, ovvero c b (mod p) oppure c b (mod p). □

Proposizione 2.4

2

I residui quadratici modulo p si ottengono calcolando b modulo p per il solo intervallo

≤ ≤ − − < < −

1 b ( p 1

) / 2. Gli altri quadrati per ( p 1

) / 2 b p 1 si ripetono in ordine inverso, pertanto esattamente metà dei residui non nulli (modulo p) sono residui quadratici (modulo p).

Dimostrazione

2 2

− ≡

Basta osservare che, quindi i residui che si ottengono facendo variare

p b b p

( ) (mod )

≤ ≤ −

1 b ( p 1

) / 2 si ripetono in senso inverso rispetto a quelli ottenuti facendo variare b

− < < −

nell’intervallo ( p 1

) / 2 b p 1. Non ci possono essere due residui quadratici congruenti

′ ′

′ ′ ′

′

≤ < ≤ − − < − < − ≤ −

generati da 1 b b ( p 1

) / 2 o da ( p 1

) / 2 ( p b ) ( p b ) p 1 perché essendo

′

′ ′

′ ′ ′

′ ′

− < − =

b b p se p | b b segue che b b, quindi i residui quadratici sono esattamente metà dei residui quadratici non nulli. □

Pagina 6 di 51

R. Volpe – Note sulla teoria dei residui quadratici Versione MM01-6 giugno 2004

Il simbolo di Legendre e il criterio di Eulero

Definizione 3.1

Il simbolo di Legendre è definito come segue:

a

 

p

 

a 2

  = +

1 se p | a e ha soluzioni.

x a p

(mod )

/

 

p

 

a 2

  = −

1 se p | a e non ha soluzioni.

x a p

(mod )

/

 

p

 

a

  = 0 se p | a.

 

p

 

Proposizione 3.2

Sia un primo dispari:

p    

a b

   

≡ ⇒ =

(a) a b (mod p).

   

p p

   

a −

p

( 1

) / 2

  ≡

Criterio di Eulero:.

(b) a (mod p)

 

p

 

+ ≡

 1 se p 1 (mod 4)

 

− 1 −

p

( 1

) / 2

  = − =

( 1)

(c).



  − ≡

1 se p 3 (mod 4)

p

  

   

 

ab a b

   

 

=

(d).

   

 

p p p

   

 

Dimostrazione

2 2

≡ ≡ ≡

(a) Se a b (mod p) allora se allora anche e viceversa, perché

x a p x b p

(mod ) (mod )

a b

2 2    

− = − + − =

x a x b b a, quindi.

   

p p

   

{ }

[ ] [ ]

*

Φ ℤ ℤ Φ

= = −

(b) Sia / p il campo delle classi di resto modulo p e 1,..., p 1 il relativo gruppo moltiplicativo associato (vedi [A] oppure [MA]).

{ }

[ ] [ ] [ ] [ ] [ ]

{ } { }

* *

Φ Φ

∈ − · = − = − =, per

x p allora

Consideriamo 1

,..., 1 x 1,..., p 1 x,..., x ( p 1

)

1 p p

1 1 1

p p ′

−

cui uno ed uno solo dei numeri x, 2x,…, ( p 1

)

x è congruente ad a. Chiamiamo x l’unico

1 1

′ ≡

numero per cui (mod )

x x a p. Fissato a con p | a consideriamo separatamente i due

/

1 1

casi che possono presentarsi:



 a 

 = 1

¾ 

 p 

 2 2

≡ ≡

In tal caso esistono esattamente due soluzioni di, cioè, e

X a p c a p

(mod ) (mod )

2 − ≡ − −

− ≡, quindi c ( p c ) a (mod p) i rimanenti p 3 elementi di

p c a p

( ) (mod )

{ } { } ( )

′

− − −

1

,

2

,..., p 1 c, p c sono costituiti da coppie di interi distinti x, x′ tali che

1 1

′ ≡ (mod )

x x a p.

1 1 · · · − = −

Segue che 1 2 ... ( p 1

) ( p 1

)! commutando i fattori del prodotto risulta congruente al

− −

p p

3 1

− · = −

numero a a a.

2 2

−

p

( 1

) / 2

− ≡ −

In sintesi: p a p

( 1

)! (mod )

Pagina 7 di 51

R. Volpe – Note sulla teoria dei residui quadratici Versione MM01-6 giugno 2004

 

a

  = −

1

¾  

p

  ( )

′ ′

− ≡

In tal caso esistono ( p 1

) / 2 coppie x, x′ tali che x x′ a (mod p). Quindi in tal caso si ha la congruenza:

1 1 1 1

−

p

( 1

) / 2

− ≡.

p a p

( 1

)! (mod ) 2

= ≡

Come caso particolare abbiamo il teorema di Wilson per a 1, infatti ha

x p

1 (mod )

= ±

come soluzioni x 1 quindi abbiamo:

− ≡ −

( p 1

)! 1 (mod p)

Infine ricordando la definizione di simbolo di Legendre abbiamo la formula cercata:

 

a −

p

( 1

) / 2

  ≡.

a (mod p)

 

p

  = −

(c) Come applicazione del punto (b) abbiamo per a = 1 che:

 

− 1 −

p

( 1

) / 2

  ≡ − quindi

( 1) (mod p)

 

p

  − ≡ −

Se ( p 1

) / 2 è pari cioè p 1 (mod 4) allora −1 è un residuo quadratico modulo p.

− ≡ −

Se ( p 1

) / 2 è dispari cioè p 3 (mod 4) allora −1 non è un residuo quadratico modulo p.

(d) Ecco una ulteriore applicazione di (b):

   

 

ab a b

− − −

p p p

( 1

) / 2 ( 1

) / 2 ( 1

) / 2

   

 

≡ ≡ ≡

ab a b

( ) (mod p)

   

 

p p p

   

 

   

       

ab a b ab a b

   

       

− ≤ − ≤ =

>

p

siccome 2 2 e segue che. □

2

   

       

p p p

p p p

   

       

Corollario 3.3

−   

a a

   

≡ =

Se p 1 (mod 4) allora per tutti gli a.

   

p p

   

−   

a a

   

≡ = −

Se p 3 (mod 4) allora per tutti gli a.

   

p p

   

Dimostrazione

≡ −

Se p 1 (mod 4) allora ( p 1

) / 2 è pari quindi applicando il criterio di Eulero dato che

− −

p p

( 1

) / 2 ( 1

) / 2

− =

a a segue il risultato.

( ) ≡ −

Se invece p 3 (mod 4) allora ( p 1

) / 2 è dispari quindi applicando il criterio di Eulero dato che

− −

p p

( 1

) / 2 ( 1

) / 2

− = − segue il risultato. □

a a

( )

La risposta alla domanda “quali primi p hanno 2 come residuo quadratico” ci porta ad uno dei più importanti risultati della teoria elementare dei numeri. Sperimentalmente per i primi piccoli

±

possiamo congetturare la risposta “i primi congruenti 1 (mod 8)”

 

2

  = =

per p 7, 17, 23, 31, 41, 47, 71 ...

1

 

p

 

 

2

  = − =

per p 3, 5, 11, 13, 19, 29, 37, 43 ...

1

 

p

   

a

 

Più in generale, per a fissato, dipende dal residuo di p modulo 4

a, e questa è proprio una delle forme della legge della reciprocità quadratica di Gauss, inizialmente congetturata da Eulero.

 

p

 

Pagina 8 di 51

R. Volpe – Note sulla teoria dei residui quadratici Versione MM01-6 giugno 2004

La legge di reciprocità quadratica (LRQ)

Proposizione 4.1 - Lemma di Gauss

Sia p un primo dispari e a un intero non divisibile per p. Si consideri il minimo residuo dell’intero ka per 1 ≤ k ≤ ( p 1

) / 2 ridotto in modo da essere compreso nell’intervallo [ p / 2, p / 2 ].

Se il numero di questi residui che sono negativi è s, allora:

 

a s

  = (−

1

) .

 

p

 

Dimostrazione

Abbiamo che per applicazione del criterio di Eulero:

 

− − −

( 1

) ( 1

) ( 1

)

p p p a

−

p

( 1

) / 2  

· · · · = =

( 1 a ) ( 2 a )...( a ) ! !

 

2 2 2 p

 

inoltre risulta:

− −

( p 1

) ( p 1

)

s

· · · · = −

(

1 a ) (

2 a )...( a ) ( 1

)! infatti:

2 2

− −

p 1 p 1

′

′ ′ − ≤ − ≤

≡ − k k

Se ka k a (mod p), dato che p | a, allora p | (

k k) da cui essendo

/

¾ 2 2

′

=

segue che k k.

′ ′

≡ − +

Se per assurdo ka k a (mod p), dato che p | a, allora p | (

k k) da cui essendo

/

¾ ′ ′ ′

< + < = − >

0 k k p segue l’assurdo k k dato che k

k 0.

≡

Non può risultare ka 0 (mod p) dato che p | a e p | k.

/ /

¾ ≤ ≤ −

Quindi ciascuno dei numeri ka per 1 k ( p 1

) / 2 è congruo ad uno ed uno solo dei numeri dei

− −

 

( p 1

) ( p 1

)

= − − −

A, ..., 2

, 1

, 0

, 1

, 2

,... , e numeri

numeri non nulli del sistema di residui modulo p:  

2 2

  −

( p 1

)

· · · ·

differenti sono congruenti a residui differenti in valore assoluto. Per cui (

1 a ) (

2 a )...( a )

2

−

( p 1

) s

ha come valore assoluto !, e come segno il prodotto dei segni dei residui negativi, cioè.

(− 1

)

2

Per semplice uguaglianza delle due formule sopra semplificando il fattore comune si ottiene il risultato. □

Siamo ora in grado di rispondere alla nostra domanda relativa a primi dispari che hanno come residuo quadratico 2.

Proposizione 4.2

Sia un primo dispari allora:

p + ≡ ±

 1 se p 1 (mod 8)

 

2 2 −

p