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)$

$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. 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. Supoponiamo 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.

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.