Teoria dei numeri
Lezione del giorno 30 aprile 2009
Abbiamo visto che, dati un primo p>2 ed un numero naturale a>1 non multiplo di p, per calcolare il simbolo di Legendre (a/p) basta fattorizzare a in prodotto di potenze di primi distinti:
a = p1k1p2k2....prkr (con pi primi distinti tutti p) e calcolare poi :
(a/p) =
r
k i1
i
i
/p) (p dispari
Dunque il calcolo di (a/p) si riconduce al calcolo di (q/p) dove q è un generico primo p.
Affronteremo prima il caso q=2.
Teorema.
Se p è primo >2 si ha: (2/p) = (1)(p21)/8
Dimostrazione:
Essendo p dispari, p-1 è pari. Elenchiamo i numeri naturali pari (p-1) in due modi diversi:
2,4, ……,(p-3), (p-1) (modo naturale)
(p-1), 2, (p-3), 4 ……. (ultimo, primo, penultimo, secondo,……) Rispetto al secondo ordinamento valgono le seguenti congruenze modulo p:
p-1-1 (mod p) 22 (mod p) p-3-3 (mod p) 44 (mod p) etc…..
che si possono riscrivere nel modo seguente:
p-11(-1)1 (mod p) 22(-1)2 (mod p) p-33(-1)3 (mod p) 44(-1)4 (mod p) etc…..
Se moltiplichiamo membro a membro tali congruenze, a primo membro si otterrà il prodotto di tutti i numeri naturali pari (p-1) ossia il numero:
24…..(p-3)(p-1)=(21)(22)…..(2(p-3)/2)(2(p-1)/2)=2(p-1)/2[(p-1)/2]!
mentre a secondo membro si otterrà il numero:
(1 2 …. (p-1)/2) (-1)1+2+3+….+(p-1)/2 = [(p-1)/2]!(1)(p21)/8
(dove si è sfruttata la formula k(k+1)/2 che dà la somma dei primi k naturali, con k=(p-1)/2).
Si ottiene dunque la congruenza modulo p:
2(p-1)/2[(p-1)/2]! [(p-1)/2]!(1)(p21)/8 (mod p) Da ciò si ha che:
p è divisore di [(p-1)/2]![ 2(p-1)/2 -(1)(p21)/8]
ma p non è divisore di [(p-1)/2]! (perché [(p-1)/2]! é un prodotto di naturali tutti <p dunque tutti non multipli di p), e allora p è divisore della differenza [ 2(p-1)/2 -(1)(p21)/8], ossia :
2(p-1)/2 (1)(p21)/8 (mod p)
Per la proprietà 1) del simbolo di Legendre, si ha (2/p) (1)(p21)/8 (mod p)
I due membri di tale congruenza sono uguali a 1, dunque non possono essere diversi far loro ( la congruenza +1-1 (mod p) è impossibile perché p>2) e si ha la tesi.
Abbiamo dimostrato il seguente risultato: se p è primo >2 si ha (2/p) = (1)(p21)/8.
Dal tale risultato segue in pratica che (2/p)= 1 a secondo se (p2-1)/8 è pari o dispari. Ma considerando la classe [p] in Z8 si ha [p]=[t] con t=0,1,…,7, p=t+8k con k naturale, ed essendo p dispari anche t è dispari, cioè gli unici valori possibili di t sono t=1,3,5,7. Si ha allora:
(p2-1)/8 = (t2-1)/8+(8k2+2tk)
Dunque (p2-1)/8 è pari se e solo se (t2-1)/8 è multiplo di 2, e ciò avviene solo per t=1,7.
Riassumendo:
(2/p)=+1 se (p2-1)/8 è pari cioè se p1,7 (mod 8) (2/p)=-1 se (p2-1)/8 è dispari cioè se p3,5 (mod 8)
Per il calcolo del simbolo di Legendre (q/p) nel caso di q,p primi distinti entrambi > 2 può essere utile il seguente Teorema (di cui si omette la dimostrazione):
Legge di reciprocità quadratica di Gauss.
Se p,q sono primi >2 distinti si ha:
(p/q)(q/p) = (-1)(p-1)(q-1)/4
Si può allora calcolare uno dei numeri (p/q), (q/p) conoscendo l’altro: infatti moltiplicando l’eguaglianza precedente per esempio per (p/q) (ricordando che (p/q)2=(1)2=1) si ha
(q/p) = (-1)(p-1)(q-1)/4(p/q)
Tutte le considerazioni già fatte permettono di costruire un algoritmo per il calcolo di (a/p), quando p>2 è un primo ed a è un numero naturale qualunque non multiplo di p:
- si rende a<p sostituendo a con la sua riduzione modulo p (ricordare che se ab (mod p) allora (a/p)=(b/p))
- si fattorizza a in prodotto di potenze di primi distinti:
a = p1k1p2k2....prkr (pi primi distintip) in modo da avere:
(a/p) =
r
k i1
i
i
/p) (p dispari
e ricondurre il calcolo di (a/p) si riconduce al calcolo di (pi/p) - se pi=2 si usa la formula già dimostrata per (2/p)
- se pi>2 quindi pi, si usa la legge di reciprocità quadratica per ricavare (pi/p) in funzione di (p/pi), ed essendo p>pi si riduce p modulo pi , si fattorizza tale riduzione in prodotto di primi, e si itera il procedimento.
L’algoritmo precedente riconduce il calcolo a numeri sempre più piccoli: al limite alla fine si tratta di calcolare un simbolo di Legendre del tipo (2/p)=(1)(p21)/8 o (1/p)=1 (perché 112 (mod p)).
Esempio:
Calcoliamo (338/131).
Riducendo 338 modulo 131 si ottiene 76, quindi si deve calcolare (76/131).
I fattori primi di 76 sono 2 (con molteplicità 2) e 19 (con molteplicità 1), quindi (76/131)=(19/131).
Per la legge di reciprocità quadratica (essendo [(19-1)/2][(131-1)/2] dispari): (19/131)=-(131/19).
Riducendo 131 modulo 19 si ottiene 17, da cui (131/19)=(17/19).
Per la legge di reciprocità quadratica (essendo [(17-1)/2][(19-1)/2] pari): (17/19)=(19/17).
Riducendo 19 modulo 17 si ottiene 2, da cui (17/19)=(2/17).
Infine (2/17)=+1 (perché 171 (mod 8)).
Riassumendo si ha (338/131)= -1 (quindi 331 non è resto quadratico modulo 131).
