Aritmetica modulare/Radici primitive

Wikibooks, manuali e libri di testo liberi.
Jump to navigation Jump to search

In questo modulo ci si concentrerà sul gruppo moltiplicativo dell'anello .

Terminologia[modifica]

Dal piccolo teorema di Fermat sappiamo che per ogni x ed n (con x ed n coprimi) si ha

Può tuttavia esistere un numero tale che

Se h è il minore intero possibile con questa caratteristica, si dice che h è l'ordine di x modulo n; se in particolare , allora si dice che x è una radice primitiva modulo n (in teoria dei gruppi una radice primitiva viene denominata "generatore del gruppo"). Ad esempio 5 ha la radice primitiva 2, perché

mentre 8 non ne ha una, in quanto

mentre . Sorge quindi il problema di stabilire quali n possiedono una radice primitiva e quali no.

Prime proprietà dell'ordine[modifica]

Da ora in poi supporremo sempre n fissato e x coprimo con n, e porremo .

Supponiamo che x abbia ordine h. Una prima proprietà, banale, è che h è un divisore di N. Suppooniamo infatti che MCD(h,N)= k < h. Allora la congruenza

è risolubile per un y >1. Quindi

e quindi k dovrebbe essere l'ordine di x, essendo minore di h. Questo è assurdo, e h divide N.

Supponiamo ora che x e y abbiamo ordine rispettivamente h e k, e che h e k siano coprimi. Allora xy ha ordine hk. È infatti ovvio, da quanto detto prima, che ne è un divisore, perché

Supponiamo ora che l'ordine di xy sia HK, dove H divide h e K divide k; H e K sono coprimi, essendo i loro multipli. Supponiamo h = Hj; elevando xy alla HjK, si ha

e anche

e quindi hK è un multiplo di k; essendo h coprimo con k, si deve avere che K è un multiplo di k, e quindi, essendone anche un divisore, k = K. Allo stesso modo h = H, e l'ordine di xy è hk.

Consideriamo ora il caso dell'ordine di un numero x rispetto a due moduli coprimi n ed m. Sia h l'ordine di x rispetto ad n e k l'ordine di x rispetto a m. Allora l'ordine di x rispetto a nm è il minimo comune multiplo tra h e k. Infatti, dire che

equivale a dire

e questo è possibile solo se l è multiplo sia di h che di k, e in particolare vale per ogni multiplo comune di h e di k: quindi il loro multiplo comune più piccolo, cioè il loro m.c.m., è l'ordine di x rispetto a nm.

Numeri primi[modifica]

Supponiamo ora che n è un numero primo, e denotiamolo quindi con p. Dimostreremo che per ogni p esiste una radice primitiva.

, quindi gli ordini dei vari elementi sono divisori di p -1. Possiamo fattorizzare quest'ultimo numero, ottenendo

Se riuscissimo a trovare un gruppo di elementi tali che ha ordine per ogni i, allora il prodotto avrebbe, per le proprietà dimostrate precedentemente, ordine esattamente p -1.

Un di ordine precisamente soddisfa la congruenza

ma non

Consideriamo il polinomio : per il piccolo teorema, ha esattamente p -1 zeri distinti (cioè tutti gli elementi di eccetto lo zero), e poniamo . Si ha per un m; ponendo , risulta evidente che

In x, i due polinomi a destra hanno grado rispettivamente e , e quindi, poiché p è primo, hanno al massimo rispettivamente e soluzioni. Ma la somma del loro numero di soluzioni deve dare p -1, quindi ne hanno esattamente tante. Ma ora la congruenza

ha al massimo soluzioni, che sono di meno di ; quindi esattamente elementi di hanno ordine . Poiché questo avviene per ogni i, per quanto detto prima, esiste un elemento che ha ordine , cioè una radice primitiva.

Potenze dei numeri primi[modifica]

Esaminiamo ora il caso delle potenze dei numeri primi, e consideriamo il caso p =2. Per n =4, 3 è una radice primitiva. L'esempio all'inizio del capitolo mostra invece che 8 non ha una radice primitiva, perché per ogni a dispari; questo implica che per ogni altra potenza di due non può esserci una radice primitiva: infatti supponiamo che questo avvenga per un , e che a sia la radice primitiva, tale che a è congruo a b modulo 8 (questa congruenza su una congruenza ha senso, perché è, per ipotesi, multiplo di 8). Allora le potenze di a sono congrue, modulo 8, alternativamente a b e ad 1, mentre dovrebbero essere congrue anche alle altre due (se b =3, ad esempio, dovrebbero essere congrue anche a 5 e a 7); quindi una radice primitiva non può esistere.

Sia ora p un primo maggiore di 2, e a una sua radice primitiva. ; inoltre, l'ordine di a modulo è un multiplo di p -1, perché per avere

si deve avere

Gli unici multipli di p -1 che dividono p (p -1) sono i due estremi, cioè gli stessi p -1 e p (p -1): se è quest'ultimo, allora a è una radice primitiva modulo ; supponiamo invece che non lo sia, e consideriamo il numero (coprimo con p) p - a. Attraverso lo sviluppo del binomio di Newton si ha

Modulo , gli unici elementi che restano sono quelli con i =p -2 e i =p -1:

che è congruo a 1 modulo se e solo se

che è impossibile perché a è coprimo con p, essendone una radice primitiva. Quindi o a o p - a è una radice primitiva per , o, detto in altri termini, questa esiste sempre.

Dimostreremo ora che, se a è una radice primitiva per , allora è una radice primitiva anche per per ogni k >2. Procediamo per induzione: se k =2 questo è vero per ipotesi (abbiamo dimostrato prima che a esiste) e inoltre a è una radice primitiva modulo p. Supponiamo che il teorema sia valido per ogni k fino a K escluso. In questo caso l'ordine di a può essere solamente oppure . Inoltre abbiamo

Elevando a alla si ha

e calcolando modulo

Se ora l non è divisibile per p, abbiamo dimostrato che a è una radice primitiva modulo ; se invece a è divisible per p si ha

e quindi a ha ordine modulo , contro l'ipotesi che a sia una radice primitiva, questo è assurdo, e quindi a è una radice primitiva modulo . Per induzione, segue che a è una radice primitiva per ogni , k >2.

Numeri divisibili da più di un primo[modifica]

Consideriamo ora un numero n che non è potenza di un numero primo, fattorizzandolo come . La funzione di Eulero è moltiplicativa, quindi l'ordine necessario per essere una radice primitiva è ; se x non è una radice primitiva modulo (qualunque p), a maggior ragione non lo potrà essere modulo n, perché vi sono degli elementi modulo che non genera (sia b uno di questi): se non è mai congruo a b modulo , non lo potrà mai essere modulo n, e quindi x non è una radice primitiva.

Consideriamo ora un x che è una radice primitiva modulo per ogni i. Questa esiste, perché di ognuna esistono le radici primitive , e a questa s-upla è possibile assegnare un elemento di (vedi il capitolo sulle congruenze lineari). Affinché il suo ordine modulo n sia il prodotto degli ordini, questi devono essere tutti coprimi tra loro. Tuttavia, se p è un primo dispari, è pari, e così la funzione di Eulero delle sue potenze. Anche , per k >1, è pari: quindi, per avere una radice primitiva, n può contenere nella sua fattorizzazione al massimo un primo dispari (eventualmente elevato a qualche potenza) e 2.

Ricapitolando, gli unici n che hanno una radice primitiva sono:

  • 2 e 4;
  • per p primo dispari e k qualsiasi;
  • per p primo dispari e k qualsiasi.

Indici[modifica]

Consideriamo ora una radice primitiva g per un numero primo p: per definizione, i numeri

corrispondono, in qualche ordine, ai numeri 1,2,...,p -1. Se , k è dello l'indice di x rispetto alla radice primitiva g.

Sia ora . Le potenze di x saranno i numeri

dove gli esponenti possono essere ridotti modulo p -1. Fissato un altro numero y, la congruenza

(dove l'incognita è k) è equivalente a

ovvero, poiché possiamo ridurre modulo p -1 gli esponenti,

che è risolubile, come sappiamo, se e solo se l'MCD(a,p -1) divide b. In particolare, se a è coprimo con p -1, allora è risolubile per ogni b, e viceversa. In questo caso, le potenze di x corrispondono a tutte le potenze di g, ovvero a tutto , e quindi x è un'altra radice primitiva per p. Quindi esistono esattamente radici primitive.

Lo stesso ragionamento si può applicare agli altri numeri n per i quali esiste una radice primitiva: in questo caso esse sono in numero di .