Lezione del giorno 23 aprile 2009
Sia A un campo: possiamo considerare il gruppo moltiplicativo A*=A-{0A} degli elementi invertibili di A rispetto al prodotto.
Teorema.
Se A è un campo finito, il gruppo moltiplicativo A*=A-{0A} è un gruppo ciclico.
Dimostrazione:
Sia G=A*, ed n=G: la tesi è che esiste un generatore del gruppo G, cioè un elemento aG di periodo = n.
Sia S l’insieme di tutti i naturali divisori di n. Per ogni dS sia Sd il sottoinsieme di G formato dagli elementi di G di periodo d (a priori può essere Sd=). Supponiamo che Sd, e calcoliamo la cardinalità di Sd .Fissiamo un elemento a in Sd (quindi a ha periodo d): le potenze distinte di a sono in numero di d e sono a0, a1,…,ad-1. Ognuna di tali potenze è radice del polinomio di grado d:
f(x)=xd-1AA[x]; infatti (ai)d=(ad)i=1A. Essendo A un campo, il polinomio f(x) ha in A al più d radici, dunque le d potenze di a esauriscono tutte le radici di f(x) in A.
Ma un elemento qualunque bSd è radice di f(x) (perché b ha periodo d dunque bd=1A) .
Si conclude che ogni elemento di Sd è una potenza di a. Per costruzione gli elementi di Sd sono le potenze di a che hanno periodo d, dunque, per un risultato precedente sono in numero di (d).
Dunque Sd ha cardinalità (d) (se è ). Al variare di dS, i sottoinsiemi Sd sono banalmente a due a due disgiunti e la loro unione è G (se yG, detto d il periodo di y, si ha d divisore di n, dS, ySd).
Dunque:
n = G =
S d
Sd =
n d Sd
Per un risultato precedente si ha n=
n d
(d)
=
n d
Sd
. Ma Sd=0 (se Sd=) oppure Sd=(d) (se Sd). Dall’eguaglianza precedente segue che nessun Sd è vuoto (altrimenti
n d Sd
<
n d
(d)
) e in particolare Sn, ossia esiste un elemento in G di periodo n, e si ha la tesi.
Nota: La dimostrazione precedente non è costruttiva, perché non fornisce un algoritmo per il calcolo di un generatore del gruppo A* .
Teorema.
Dato un intero n>1:
l’anello Zn è campo Û n è primo Dimostrazione:
Ricordiamo che in Zn una classe [a][0] ha inverso se e solo se a,n sono coprimi.
(Þ) Se per assurdo n non fosse primo, esisterebbe un divisore non banale d di n con 1<d<n, e la classe [d][0] non avrebbe inverso (essendo mcd(d,n)=d>1) contro l’ipotesi che Zn è campo
(Ü) Le classi [0] in Zn sono [1],[2],..,[n-1] ed essendo n coprimo con 1,2,…,n-1 (perché non sono multipli di n ed n è primo) tutte queste classi hanno inverso, quindi Zn è campo.
Come conseguenza dei risultati precedenti:
Teorema di Gauss (il caso n primo).
Se n è primo, il gruppo moltiplicativo Zn* è ciclico (quindi esiste qualche radice primitiva modulo n).
Dimostrazione:
Segue immediatamente dai 2 Teoremi precedenti..
Nota: La dimostrazione dell’esistenza di un generatore per il gruppo moltiplicativo A* di un campo finito A non è costruttiva, dunque in particolare non fornisce un algoritmo per calcolare una radice primitiva modulo n, quando n è primo: a tutt’oggi non è noto nessun algoritmo di complessità polinomiale che risolva il problema.
In ogni caso, se n è primo, sappiamo che il numero di radici primitive modulo n è ((n))=(n-1).
Per esempio se n=11, il numero di radici primitive modulo 11 è (10)=4.
Teorema di Gauss (il caso del quadrato di un numero primo).
Se n=p2 con p primo, il gruppo moltiplicativo Zn* è ciclico (quindi esiste qualche radice primitiva modulo n).
Dimostrazione.
Poiché tratteremo di classi di congruenza con diversi moduli, conveniamo di indicare, per un generico modulo m>1, la classe di congruenza rappresentata dall’intero a modulo m con [a]m. Sia a una radice primitiva modulo p (che esiste per il risultato precedente): (p)=(p-1) è il periodo di [a]p nel gruppo moltiplicativo Zp* quindi (n-1) è il minimo esponente positivo tale [a]pn-1=[1]p
cioè tale che ap-11 (mod p) . Vi sono 2 casi possibili:
1) ap-1 non è congruo 1 modulo n 2) ap-1 è congruo 1 modulo n
Supponiamo che si verifichi il caso 1): sia d il periodo di [a]n nel gruppo moltiplicativo Zn*: per una proprietà del periodo si ha d(n) cioè dp(p-1).
Essendo ad1 (mod n), a maggior ragione si ha ad1 (mod p), perché p è divisore di n, dunque [a]pd=[1]p e per una proprietà del periodo di [a]p in Zp* si deduce che (p-1)d.
Dunque p(p-1)=hd, d=(p-1)s con h,s interi: da ciò p=hs, s=1 oppure s=p. Ma non può essere s=1, altrimenti sarebbe d=(p-1), ap-11 (mod n), in contraddizione con il caso 1).
Dunque s=p, d=p(p-1): il periodo di [a]n nel gruppo moltiplicativo Zn* è allora (n)=p(p-1), e l’intero a è una radice primitiva modulo n.
Supponiamo che si verifichi il caso 2): consideriamo l’intero b=a+p. Sviluppando la potenza con la regola di Newton si ha:
bp-1 = (a+p)p-1 = p 1 j j
1 p
0 j
p j a
1
p
= an-1+(p-1)pap-2+p2m (con m intero)
Tenendo conto che ap-11 (mod n) , si hanno le seguenti congruenze modulo n : bp-1 ap-1+(p-1)pap-2 = ap-1+p2ap-2- pap-2 1- pap-2 (mod n)
Si conclude che bp-1 non è congruo 1 modulo n (se così fosse sarebbe p2pan-2, quindi pan-2 ossia pa contro l’ipotesi che [a]p Zp*). Ma [a]p=[a+p]p=[b]p dunque anche b é una radice primitiva modulo p.
Sostituendo a con b nello stesso ragionamento fatto sopra, si ricade nel caso 1), e si ha che b è una radice primitiva modulo n .
Nota: dalla dimostrazione precedente si ricava che, se a è una radice primitiva modulo p allora vi sono solo 2 casi possibili (che corrispondono ai casi 1) e 2)): a è anche radice primitiva modulo p2, oppure (a+p) è radice primitiva modulo p2 .
