Teoria dei numeri Lezione del giorno 7 maggio 2008 Resti quadratici. Siano p un numero primo, a un naturale non multiplo di p. Si ha allora a,p coprimi, dunque [a] appartiene al gruppo moltiplicativo Z

Teoria dei numeri

Lezione del giorno 7 maggio 2008 Resti quadratici.

Siano p un numero primo, a un naturale non multiplo di p.

Si ha allora a,p coprimi, dunque [a] appartiene al gruppo moltiplicativo Z

* degli elementi invertibili di Z

.

Diremo che a è un resto quadratico modulo p se esiste un naturale b tale che ab

(mod p) (quindi se a è un “quadrato modulo p”). Notiamo che in tal caso anche il naturale b è ovviamente non multiplo di p, dunque [b] Z

* e si ha [a]=[b

]=[b]

: in pratica a è resto quadratico modulo p se e solo se [a] è un quadrato perfetto in Z

* (quindi la proprietà di essere un resto quadratico modulo p è relativa alla classe di congruenza modulo p, non al singolo naturale a).

Esempio.

Troviamo quali numeri naturali (non multipli di p=7) sono resti quadratici modulo 7.

Si ha Z

* = {[1], [2], [3], [4], [5], [6]}, e i quadrati delle classi sono [1]

=[6]

=[1], [2]

=[5]

=[4], [3]

=[4]

=[2].

Quindi i resti quadratici modulo 7 sono i numeri naturali a tali che a1,2,4 (mod 7).

Per p=2 la situazione dei resti quadratici è banale: si ha Z

*={[1]}, [1]

=[1], e tutti i naturali coprimi con 2 (cioè dispari) sono resti quadratici modulo 2.

Quindi studieremo la teoria dei resti quadratici solo nel caso di un numero primo p>2 (quindi p dispari).

Criterio di Eulero.

Sia p>2 un primo ed a un naturale non multiplo di p. Allora:

a è resto quadratico modulo p  a

1 (mod p) Dimostrazione:

() Per ipotesi esiste [b]  Z

* tale che [a]=[b]

. Per il Piccolo Teorema di Fermat si ha:

[1]=[b]

=[a]

e si ottiene la tesi.

() Per il Teorema di Gauss, il gruppo Z

* è ciclico, generato da un elemento [x] di periodo uguale alla cardinalità (p-1) di Z

*.

Ogni elemento di Z

* è potenza di [x], e in particolare [a]=[x]

.

Per ipotesi si ha [1]=[a]

=([x]

)

=[x]

, dunque t(p-1)/2 è multiplo del periodo (p-1) di [x], cioè t è multiplo di 2, t=2k, da cui ([x]

)

=[x]

=[a], ed a è resto quadratico modulo p.

Come conseguenza del criterio di Eulero, si ha che la verifica se a è resto quadratico modulo p si può effettuare con un algoritmo di complessità polinomiale (utilizzando l’esponenziazione modulare per verificare se a

modp=1).

Osservazione: Se p>2 é un primo ed a un naturale non multiplo di p, e se a non è resto quadratico modulo p, cosa possiamo dire di a

? Per il Piccolo Teorema di Fermat si ha (a

)

1 (mod p), dunque, per una proprietà già osservata durante il test di Rabin-Miller, si ha a

1 (mod p), e per il criterio di Eulero si conclude che a

-1 (mod p).

Quindi la situazione è la seguente:

a è resto quadratico modulo p  a

1 (mod p)

a non è resto quadratico modulo p  a

-1 (mod p)

Introduciamo allora il simbolo di Legendre (a/p), definito solo per p primo >2 ed a naturale non multiplo di p:

(a/p) = +1 se a è resto quadratico modulo p (a/p) = -1 se a non è resto quadratico modulo p Proprietà:

Sia p primo >2.

1) Se a è un naturale non multiplo di p si ha a

(a/p) (mod p) Discende banalmente da quanto osservato sopra.

2) Se a,b sono naturali non multipli di p (quindi anche ab non è multiplo di p): (ab/p)=(a/p)(b/p).

Infatti per la proprietà 1) si ha (ab/p)(ab)

a

b

(a/p)(b/p) (mod p), ma i valori possibili di ognuno dei 2 numeri (a/p)(b/p), (ab/p) sono 1, dunque la congruenza precedente è in effetti un’eguaglianza (perché la congruenza 1-1 (mod p) è impossibile nel caso p>2).

3) Se a,b sono naturali non multipli di p e se ab (mod p) allora (a/p)=(b/p).

Discende banalmente dall’osservazione che la proprietà di essere resto quadratico dipende solo dalla classe di congruenza modulo p.

Siano dunque a>1 un numero naturale, p>2 un primo e scomponiamo a in prodotto di potenze di primi distinti:

a = p

p

....p

(notare che ogni p

p dunque p

non è multiplo di p, ed esiste (p

/p)) Per la 2) si ha :

(a/p) = 

 r

1 i

i/p)kⁱ (p

Ma nella formula precedente: se k

è pari (p

/p)

=

=+1, e se k

è dispari (p

/p)

=(p

/p), dunque in totale si ha :

(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 primo p.

Affronteremo prima il caso q=2.

Teorema.

Se p è primo >2 si ha: (2/p) =

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) 22 (mod p) p-3-3 (mod p) 44 (mod p) etc…..

che si possono riscrivere nel modo seguente:

p-11(-1)

(mod p)

22(-1)

(mod p)

p-33(-1)

(mod p)

44(-1)

(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:

24…..(p-3)(p-1)=(21)(22)…..(2(p-3)/2)(2(p-1)/2)=2

[(p-1)/2]!

mentre a secondo membro si otterrà il numero:

(1 2 …. (p-1)/2)  (-1)

= [(p-1)/2]!

(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]!

(mod p) Da ciò si ha che:

p è divisore di [(p-1)/2]![ 2

-

]

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

-

], ossia :

2



(mod p)

Per la proprietà 1) del simbolo di Legendre, si ha (2/p) 

(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.