Aritmetica modulare/Radici primitive

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

Terminologia

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

$x^{\varphi (n)}\equiv 1modn$

Può tuttavia esistere un numero $h<\varphi (n)$ tale che

$x^h\equiv 1modn$

Se h è il minore intero possibile con questa caratteristica, si dice che h è l'ordine di x modulo n; se in particolare $h=\varphi (n)$, 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é

$2^1\equiv 2mod5,2^2\equiv 4mod5,2^3\equiv 3mod5,2^4\equiv 1mod5$

mentre 8 non ne ha una, in quanto

$1^2\equiv 1mod8,3^2\equiv 1mod8,5^2\equiv 1mod8,7^2\equiv 1mod8$

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

Prime proprietà dell'ordine

Da ora in poi supporremo sempre n fissato e x coprimo con n, e porremo $N=\varphi (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 kmodN$

è risolubile per un y >1. Quindi

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

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}modn\equiv 1modn$

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}modn$

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

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 1modnm$

equivale a dire

$\{\begin{array}{c}{x}^l\equiv 1modn\\ x^l\equiv 1modm\end{array}$

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

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

$\varphi (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,\dots ,x_s$ tali che $x_i$ ha ordine $a_i$ per ogni i, allora il prodotto $x_1{x}_2{x}_3\cdots x_s$ avrebbe, per le proprietà dimostrate precedentemente, ordine esattamente p -1.

Un $x_i$ di ordine precisamente $a_i$ soddisfa la congruenza

$x^{q^{a_i}}\equiv 1modp$

ma non

$x^{q^{a_i-1}}\equiv 1modp$

Consideriamo il polinomio $P(x)=x^{p-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=q^{a}w$ 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 $q^a$ e $p-1-q^a$, e quindi, poiché p è primo, hanno al massimo rispettivamente $q^a$ e $p-1-q^a$ 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 1modp$

ha al massimo $q^{a-1}$ soluzioni, che sono di meno di $q^a$; quindi esattamente $q^a-q^{a-1}$ elementi di ${\mathbb{Z}}_p$ hanno ordine $q^a$. 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.

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

$a^k\equiv 1mod{p}^2$

si deve avere

$a^k\equiv 1modp$

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 $p^2$; 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}(\genfrac{}{}{0ex}{}{p-1}{i})(-1{)}^i{a}^i{p}^{p-1-i}$

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

$(p-a{)}^{p-1}\equiv (\genfrac{}{}{0ex}{}{p-1}{p-2})(-1{)}^{p-2}{a}^{p-2}p+(\genfrac{}{}{0ex}{}{p-1}{p-1})(-1{)}^{p-1}{a}^{p-1}mod{p}^2\equiv (p-1)(-1)a^{-1}p+1mod{p}^2\equiv p{a}^{-1}+1mod{p}^2$

che è congruo a 1 modulo $p^2$ se e solo se

$p{a}^{-1}\equiv 0mod{p}^2⟺a^{-1}\equiv 0modp$

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

Dimostreremo ora che, se a è una radice primitiva per $p^2$, allora è una radice primitiva anche per $p^k$ 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 $\varphi (p^{K-1})=p^{K-2}(p-1)$ oppure $\varphi (p^K)=p^{K-1}(p-1)$. Inoltre abbiamo

$a^{\varphi (p^{K-2})}=1+l{p}^{K-2}$

Elevando a alla $\varphi (p^{K-1})$ si ha

$a^{\varphi (p^{K-1})}=a^{p^{K-2}(p-1)}=(a^{p^{K-3}(p-1)}{)}^p=(a^{\varphi (p^{K-2})}{)}^p=(1+l{p}^{K-2}{)}^p=(\genfrac{}{}{0ex}{}{p}{0})p^0+(\genfrac{}{}{0ex}{}{p}{1})l{p}^{K-2}+(\genfrac{}{}{0ex}{}{p}{2})l^2{p}^{2(K-2)}+\cdots$

e calcolando modulo $p^K$

$a^{\varphi (p^{K-1})}\equiv 1+lp{p}^{K-2}mod{p}^K\equiv 1+l{p}^{K-1}mod{p}^K$

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

$a^{\varphi (p^{K-2})}=1+l_{1}p{p}^{K-2}\equiv 1mod{p}^{K-1}$

e quindi a ha ordine $\varphi (p^{K-2})$ modulo $p^{K-1}$, contro l'ipotesi che a sia una radice primitiva, questo è assurdo, e quindi a è una radice primitiva modulo $p^K$. Per induzione, segue che a è una radice primitiva per ogni $p^k$, k >2.

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 è $\varphi (p_1^{a^1})\varphi (p_2^{a_2})\cdots \varphi (p_k^{a_k})$; se x non è una radice primitiva modulo $p^a$ (qualunque p), a maggior ragione non lo potrà essere modulo n, perché vi sono degli elementi modulo $p^a$ che non genera (sia b uno di questi): se $x^k$ non è mai congruo a b modulo $p^a$, 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,\dots ,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, $\varphi \left(p\right)=p-1$ è pari, e così la funzione di Eulero delle sue potenze. Anche $\varphi \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;
• $p^k$ per p primo dispari e k qualsiasi;
• $2p^k$ per p primo dispari e k qualsiasi.

Indici

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

$g,g^2,g^3,\dots ,g^{p-1}$

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

Sia ora $x=g^a$. Le potenze di x saranno i numeri

$g^a,g^{2a},g^{3a},\dots ,g^{(p-1)a}$

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

$x^k\equiv ymodp$

(dove l'incognita è k) è equivalente a

$g^{ak}\equiv g^{b}modp$

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

$ak\equiv bmod(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 $\varphi (p-1)$ 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 $\varphi (\varphi (n))$. Template:Avanzamento