Aritmetica modulare/Radici primitive

Indice del libro

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  .