Aritmetica modulare/Radici primitive

Wikibooks, manuali e libri di testo liberi.

Sommario
Categoria · Copertina · Bibliografia · modifica il template

Copertina Aritmetica modulare/Copertina
  1. La relazione di congruenza Aritmetica modulare/La relazione di congruenza
  2. Prime proprietà e applicazioni Aritmetica modulare/Prime proprietà e applicazioni
  3. Congruenze lineari Aritmetica modulare/Congruenze lineari
  4. Polinomi in aritmetica modulare Aritmetica modulare/Polinomi in aritmetica modulare
  5. Radici primitive Aritmetica modulare/Radici primitive
  6. Congruenze quadratiche Aritmetica modulare/Congruenze quadratiche
  7. Alcune applicazioni Aritmetica modulare/Alcune applicazioni
  8. Bibliografia Aritmetica modulare/Bibliografia
  9. Esercizi Aritmetica modulare/Esercizi

In questo modulo ci si concentrerà sul gruppo moltiplicativo dell'anello \mathbb{Z}_n.

Indice

[modifica] Terminologia

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

x^{\phi(n)}\equiv 1\mod n

Può tuttavia esistere un numero h < φ(n) tale che

x^h\equiv 1\mod n

Se h è il minore intero possibile con questa caratteristica, si dice che h è l'ordine di x modulo n; se in particolare h = φ(n), allora si dice che x è una radice primitiva modulo n. Ad esempio 5 ha la radice primitiva 2, perché

2^1\equiv 2\mod 5,~~2^2\equiv 4\mod 5,~~2^3\equiv 3\mod 5,~~2^4\equiv 1\mod 5

mentre 8 non ne ha una, in quanto

1^2\equiv 1\mod 8,~~3^2\equiv 1\mod 8,~~5^2\equiv 1\mod 8,~~7^2\equiv 1\mod 8

mentre φ(8) = 4. Sorge quindi il problema di stabilire quali n possiedono una radice primitiva e quali no.

[modifica] Prime proprietà dell'ordine

Da ora in poi supporremo sempre n fissato e x coprimo con n, e porremo N = φ(n).

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

hy\equiv k\mod N

è risolubile per un y >1. Quindi

x^k\equiv x^{aN+hy} \mod n\equiv (x^N)^a(x^h)^y\mod n\equiv 1^a 1^y\mod n\equiv 1\mod n

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é

(xy)^{hk}=(x^h)^k (y^k)^h\equiv 1^k 1^h\mod n\equiv 1\mod n

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

(xy)^{HjK}=(x^h)^k y^{hK}\equiv y^{hK}\mod n

e anche (xy)^{HjK}=[(xy)^{HK}]^j\equiv 1\mod n

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

x^l\equiv 1\mod nm

equivale a dire

\begin{cases} x^l\equiv 1 \mod n\\ x^l\equiv 1\mod m\end{cases}

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.

[modifica] Numeri primi

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

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

p-1=q_1^{a_1}q_2^{a_2}\cdots q_s^{a_s}

Se riuscissimo a trovare un gruppo di elementi x_1,x_2,\ldots,x_s tali che xi ha ordine ai per ogni i, allora il prodotto x_1x_2x_3\cdots x_s avrebbe, per le proprietà dimostrate precedentemente, ordine esattamente p -1.

Un xi di ordine precisamente ai soddisfa la congruenza

x^{q^{a_i}}\equiv 1\mod p

ma non

x^{q^{a_i-1}}\equiv 1\mod p

Consideriamo il polinomio P(x) = xp − 1 − 1: per il piccolo teorema, ha esattamente p -1 zeri distinti (cioè tutti gli elementi di \mathbb{Z}_p eccetto lo zero), e poniamo q_i=q,~a_i=a. Si ha p − 1 = qaw per un m; ponendo x^{q^a}=y, risulta evidente che

x^{p-1}-1=y^w-1=(y-1)(y^{w-1}+y^{w-2}+\cdots+y^1+1)

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

x^{q^{a-1}}\equiv 1\mod p

ha al massimo qa − 1 soluzioni, che sono di meno di qa; quindi esattamente qa − qa − 1 elementi di \mathbb{Z}_p hanno ordine qa. Poiché questo avviene per ogni i, per quanto detto prima, esiste un elemento che ha ordine q_1^{a_1}q_2^{a_2}\cdots q_s^{a_s}=p-1, cioè una radice primitiva.

[modifica] Potenze dei numeri primi

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é a^2\equiv 1\mod 8 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 2k, e che a sia la radice primitiva, tale che a è congruo a b modulo 8 (questa congruenza su una congruenza ha senso, perché 2k è, 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. φ(p2) = p(p − 1); inoltre, l'ordine di a modulo p2 è un multiplo di p -1, perché per avere

a^k\equiv 1\mod p^2

si deve avere

a^k\equiv 1\mod p

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 p2; supponiamo invece che non lo sia, e consideriamo il numero (coprimo con p) p - a. Attraverso lo sviluppo del binomio di Newton si ha

(p-a)^{p-1}=\sum_{i=0}^{p-1} \binom{p-1}{i} (-1)^i a^i p^{p-1-i}

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

(p-a)^{p-1}\equiv \binom{p-1}{p-2} (-1)^{p-2} a^{p-2} p+\binom{p-1}{p-1} (-1)^{p-1} a^{p-1}\mod p^2\equiv (p-1)(-1)a^{-1}p+1\mod p^2\equiv pa^{-1}+1\mod p^2

che è congruo a 1 modulo p2 se e solo se

pa^{-1}\equiv 0\mod p^2\iff a^{-1}\equiv 0\mod p

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

Dimostreremo ora che, se a è una radice primitiva per p2, allora è una radice primitiva anche per pk 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 φ(pK − 1) = pK − 2(p − 1) oppure φ(pK) = pK − 1(p − 1). Inoltre abbiamo

a^{\phi(p^{K-2})}=1+lp^{K-2}

Elevando a alla φ(pK − 1) si ha

a^{\phi(p^{K-1})}=a^{p^{K-2}(p-1)}=(a^{p^{K-3}(p-1)})^p=(a^{\phi(p^{K-2})})^p=(1+lp^{K-2})^p=\binom{p}{0} p^0+\binom{p}{1} lp^{K-2}+\binom{p}{2} l^2p^{2(K-2)}+\cdots

e calcolando modulo pK

a^{\phi(p^{K-1})}\equiv 1+lpp^{K-2}\mod p^K\equiv 1+lp^{K-1}\mod p^K

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

a^{\phi(p^{K-2})}=1+l_1pp^{K-2}\equiv 1\mod p^{K-1}

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

[modifica] Numeri divisibili da più di un primo

Consideriamo ora un numero n che non è potenza di un numero primo, fattorizzandolo come n=p_1^{a^1}p_2^{a_2}\cdots p_s^{a_s}. La funzione di Eulero è moltiplicativa, quindi l'ordine necessario per essere una radice primitiva è \phi(p_1^{a^1})\phi(p_2^{a_2})\cdots \phi(p_k^{a_k}); se x non è una radice primitiva modulo pa (qualunque p), a maggior ragione non lo potrà essere modulo n, perché vi sono degli elementi modulo pa che non genera (sia b uno di questi): se xk non è mai congruo a b modulo pa, non lo potrà mai essere modulo n, e quindi x non è una radice primitiva.

Consideriamo ora un x che è una radice primitiva modulo p_i^{a_i} per ogni i. Questa esiste, perché di ognuna esistono le radici primitive x_1,x_2,\ldots,x_s, e a questa s-upla è possibile assegnare un elemento di \mathbb{Z}_n (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, \phi\left(p\right)=p-1 è pari, e così la funzione di Eulero delle sue potenze. Anche \phi\left(2^k\right), 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;
  • pk per p primo dispari e k qualsiasi;
  • 2pk per p primo dispari e k qualsiasi.

[modifica] Indici

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

g,~g^2,~g^3,\ldots,g^{p-1}

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

Sia ora x = ga. Le potenze di x saranno i numeri

g^a,~g^{2a},~g^{3a},\ldots,g^{(p-1)a}

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

x^k\equiv y\mod p

(dove l'incognita è k) è equivalente a

g^{ak}\equiv g^b\mod p

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

ak\equiv b\mod (p-1)

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 \mathbb{Z}_p\setminus\{0\}, e quindi x è un'altra radice primitiva per p. Quindi esistono esattamente \phi\left(p-1\right) 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 \phi\left(\phi(n)\right).

Ricavato da "http://it.wikibooks.org/wiki/Aritmetica_modulare/Radici_primitive"
Strumenti personali