Aritmetica modulare/Radici primitive

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^{\phi (n)}\equiv 1\mod n$

Può tuttavia esistere un numero $h<\phi (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=\phi (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 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 $\phi (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=\phi (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.

Numeri primi

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

$\phi (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 $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 1\mod p$

ma non

$x^{q^{a_{i}-1}}\equiv 1\mod p$

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 1\mod p$

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 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 $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. $\phi (p^{2})=p(p-1)$; inoltre, l'ordine di a modulo $p^{2}$ è 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 $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}{\binom {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 {\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 $p^{2}$ 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 $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 $\phi (p^{K-1})=p^{K-2}(p-1)$ oppure $\phi (p^{K})=p^{K-1}(p-1)$. Inoltre abbiamo

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

Elevando a alla $\phi (p^{K-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^{2}p^{2(K-2)}+\cdots$

e calcolando modulo $p^{K}$

$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 $p^{K}$; se invece a è divisible per p si ha

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

e quindi a ha ordine $\phi (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 è $\phi (p_{1}^{a^{1}})\phi (p_{2}^{a_{2}})\cdots \phi (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},\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;
• $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},\ldots ,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},\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)$.