|
In [[matematica]], in particolare in [[aritmetica modulare]], un '''generatore modulo <math>n</math>''' èo un'''radice interoprimitiva modulo <math>n</math>''g' o semplicemente '''generatore''' se è chiaro il contesto, è un [[Numero intero|intero]] <math>g</math> le cui potenze '''(mod[[Aritmetica modulare|modulo]] <math>n)'''</math> sono congruenti con i numeri [[coprimo|coprimi]] ad ''<math>n''</math>.
I generatori modulo <math>n</math> rivestono un'importanza considerevole in [[crittografia]].
Un '''generatore''' o '''radice primitiva modulo ''n''''' è un concetto dell'[[aritmetica modulare]], in [[teoria dei numeri]]. Se ''n''≥1 è un [[numero intero|intero]], i numeri [[coprimo|coprimi]] ad ''n'', considerati modulo ''n'', costituiscono un [[gruppo (matematica)|gruppo]] rispetto all'operazione di moltiplicazione; esso viene generalmente indicato con ('''Z'''/''n'''''Z''')<sup>×</sup> oppure '''Z'''<sub>n</sub><sup>*</sup>. Esso è un [[gruppo ciclico]] se e solo se ''n'' è uguale a 2, 4, ''p''<sup>''k''</sup> o 2 ''p''<sup>''k''</sup> per un [[numero primo]] [[numero dispari|dispari]] ''p'' e ''k'' ≥ 1. Un generatore di questo gruppo ciclico è chiamato '''radice primitiva modulo ''n''''', o anche '''elemento primitivo di Z'''<sub>n</sub><sup>*</sup>. In altri termini, un generatore modulo ''n'' è un intero ''g'' tale che, in modulo ''n'',
ogni intero primo con ''n'' è congruo ad una potenza di ''g''.
Se <math>n\ge 1</math> è un [[Numero intero|intero]], i numeri [[coprimo|coprimi]] ad <math>n</math>, considerati modulo <math>n</math>, costituiscono un [[Gruppo (matematica)|gruppo]] rispetto all'operazione di moltiplicazione; esso viene generalmente indicato con <math>(\Z/n\Z)^*</math> oppure <math>\Z_n^*</math>. Esso è un [[gruppo ciclico]] se e solo se <math>n</math> è uguale a <math>2</math>, <math>4</math>, <math>p^k</math> o <math>2p^k</math> per un [[numero primo]] [[Numero dispari|dispari]] <math>p</math> e <math>k\ge 1</math>. Un generatore di questo gruppo ciclico è chiamato anche '''elemento primitivo di <math>\Z_n^*</math>.
Si consideri per esempio ''n'' = 14. Gli elementi di
Si consideri per esempio <math>n=14</math>. Gli elementi di
:('''Z'''/14'''Z''')<sup>×</sup>
:<math>(\Z/14\Z)^*,</math>
sono le classi di congruenza di
sono le classi di congruenza di <math>1</math>, <math>3</math>, <math>5</math>, <math>9</math>, <math>11</math> e <math>13</math>.
:1, 3, 5, 9, 11 e 13.
Si ha che <math>3</math> è un generatore modulo <math>14</math>, perché 3<sup>2</sup> = 9, 3<sup>3</sup> = 13, 3<sup>4</sup> = 11, 3<sup>5</sup> = 5 e 3<sup>6</sup> = 1 (modulo 14). L'unica altra radice primitiva modulo <math>14</math> è <math>5</math>.
==Trovare i generatori==
Di seguito vi è una tabella che contiene i più piccoli generatori per diversi valori di ''<math>n''</math><ref>{{OEIS|A046145}}</ref>:
{| class="wikitable"
! ''n''
|}
Non è nota nessuna formula generale ragionevolmente semplice per determinare i generatori modulo ''<math>n''</math>. Vi sono però dei metodi per individuare un generatore che sono più veloci della semplice verifica per tentativi di tutti i candidati. Se l'[[ordine moltiplicativo]] di un numero ''<math>m''</math> modulo ''<math>n''</math> è uguale alla [[funzione phiall'ordine di Eulero|φ<math>(''\Z/n''\Z)]]^*</math>, (l'ordinecioè dia '''Z'''/''<math>\phi(n'''''Z''')<sup/math>×, dove <math>\phi</supmath>) è la [[funzione phi di Eulero]], allora ''<math>m''</math> è un generatore. Si può utilizzare questoil seguente test per i generatori: calcolare <math>\phi(n)</math>. Quindi determinare i diversi fattori primi di <math>\phi(n)</math>, siano <math>p_1,\ldots,p_k</math>. Ora, per ogni elemento <math>m</math> di <math>(\Z/n\Z)^*</math>, calcolare
:<math>m^{\phi(n)/p_i}\mod n \qquad\text{ per } i=1,\ldots,k</math>
: calcolare φ(''n''). Quindi determinare i diversi fattori primi di φ(''n''), siano ''p''<sub>1</sub>,...,''p''<sub>''k''</sub>. Ora, per ogni elemento ''m'' di ('''Z'''/''n'''''Z''')<sup>×</sup>, calcolare
:<math>m^{\phi(n)/p_i}\mod n \qquad\mbox{ per } i=1,\ldots,k</math>
usando il rapido [[algoritmo]] di [[esponenziazione mediante elevamento al quadrato]]. Non appena si trova un numero ''m'' per il quale questi ''k'' risultati sono tutti diversi da 1, allora ''m'' è un generatore.
usando il rapido [[algoritmo]] di [[esponenziazione mediante elevamento al quadrato]]. Non appena si trova un numero <math>m</math> per il quale questi <math>k</math> risultati sono tutti diversi da <math>1</math>, allora <math>m</math> è un generatore.
Il numero di generatori modulo ''n'', se ne esistono, è uguale a
Il numero di generatori modulo <math>n</math>, se ne esistono, è uguale a <math>\phi(\phi(n))</math> dal momento che, in generale, un gruppo ciclico di <math>r</math> elementi possiede <math>\phi(r)</math> generatori.
:φ(φ(''n''))
A volte si può essere interessati ai generatori piccoli. Al riguardo sono stati dimostrati i seguenti risultati:
dal momento che, in generale, un gruppo ciclico di ''r'' elementi possiede φ(''r'') generatori.
*per ogni <math>\varepsilon>0</math> esistono delle costanti positive <math>C</math> e <math>p_0</math> tali che, per ogni [[Numero primo|primo]] <math>p\ge p_0</math>, esiste un generatore modulo <math>p</math> minore di <math>Cp^{1/4+\varepsilon}</math>;
A volte si può essere interessati nei generatori piccoli. Al riguardo sono stati dimostrati i seguenti risultati.
Per ogni ε>0 esistono delle costanti positive ''C'' e ''p''<sub>0</sub> tali che, per ogni [[numero primo|primo]] ''p'' ≥ ''p''<sub>0</sub>, esiste un generatore modulo ''p'' minore di
*se l'[[ipotesi di Riemann generalizzata]] è vera, allora, per ogni numero primo <math>p</math>, esiste un generatore modulo <math>p</math> minore di <math>70\ln^2 p</math>.
:''C'' ''p''<sup>1/4+ε</sup>.
== Dimostrazione dell'esistenza di un generatore modulo ''p''<sup>k</sup>, ''p'' dispari==
Se l'[[ipotesi di Riemann generalizzata]] è vera, allora, per ogni numero primo ''p'', esiste un generatore modulo ''p'' minore di
La dimostrazione dell'esistenza del generatore procede dapprima provando che essa esiste per ogni numero primo <math>p</math>, poi dimostrando che, se <math>a</math> è una radice primitiva di <math>p</math>, allora o <math>a</math> o <math>p+a</math> è una radice primitiva di <math>p^2</math>, e che questa è poi radice primitiva anche di ogni potenza successiva di <math>p</math>. Infatti, sia <math>a</math> una radice primitiva modulo <math>p</math>. Allora, per definizione di radice primitiva
:70 ([[logaritmo naturale|ln]](''p''))<sup>2</sup>.
:<math>a^{p-1}\equiv 1\mod p,</math>
I generatori modulo ''m'' rivestono un'importanza considerevole in [[crittografia]].
e <math>p-1</math> è il più piccolo esponente per cui ciò avviene. Poiché <math>\phi(p^2)=p(p-1)</math>, l'[[ordine moltiplicativo]] di <math>a</math> modulo <math>p^2</math> divide <math>p(p-1)</math>, ed è multiplo di <math>p-1</math>, e quindi può essere solamente <math>p-1</math> o lo stesso <math>p(p-1)</math>. In quest'ultimo caso <math>a</math> è una radice primitiva modulo <math>p^2</math>; altrimenti, sviluppiamo con la formula del [[binomio di Newton]]
== Dimostrazione dell'esistenza di un generatore modulo ''p''<sup>k</sup>, p dispari==
:<math>(p+a)^{p-1}=p^{p-1}+\cdots+\binom{p-1}{p-2}pa^{p-2}+a^{p-1}\equiv (p-1)pa^{p-2}+a^{p-1}\mod p^2\equiv 1-pa^{p-2}\mod p^2,</math>
La dimostrazione dell'esistenza del generatore procede dapprima provando che essa esiste per ogni numero primo ''p'', poi dimostrando che, se ''a'' è una radice primitiva di ''p'', allora o ''a'' o ''p+a'' è una radice primitiva di ''p''<sup>2</sup>, e che questa è poi radice primitiva anche di ogni potenza successiva di ''p''. Infatti, sia ''a'' una radice primitiva modulo ''p''. Allora, per definizione di radice primitiva,
:<math>a^{p-1}\equiv 1\mod p</math>
e ''p''-1 è il più piccolo esponente per cui ciò avviene. Poiché <math>\phi(p^2)=p(p-1)</math>, l'[[ordine moltiplicativo]] di ''a'' modulo ''p''<sup>2</sup> divide ''p''(''p''-1), ed è multiplo di ''p''-1, e quindi può essere solamente ''p''-1 o lo stesso ''p''(''p''-1). In quest'ultimo caso ''a'' è una radice primitiva modulo ''p''<sup>2</sup>; altrimenti, sviluppiamo con la formula del [[binomio di Newton]]
:<math>(p+a)^{p-1}=p^{p-1}+\cdots+\binom{p-1}{p-2}pa^{p-2}+a^{p-1}\equiv (p-1)pa^{p-2}+a^{p-1}\mod p^2\equiv 1-pa^{p-2}\mod p^2</math>
che non può essere <math>1</math>, perché altrimenti ''<math>p''</math> dividerebbe ''a''<supmath>''a^{p''-2}</supmath>, il che è assurdo, e quindi l'ordine di ''<math>p''+''a''</math> non è ''<math>p''-1</math>, e deve essere ''<math>p''(''p''-1)</math>, cioè abbiamo trovato una radice primitiva modulo ''p''<supmath>p^2</supmath>.
Per dimostrare la proposizione per <math>p^k</math>, con <math>k>2</math>, si procede per [[induzione]]: supponiamo che <math>a</math> sia una radice primitiva per tutti i <math>p^j</math> con <math>j<k</math>. In particolare
:<math>a^{\phi(p^{k-2})}\equiv 1 \mod p^{k-2},</math>
Per dimostrare la proposizione per ''p''<sup>k</sup>, con ''k''>2, si procede per [[induzione]]: supponiamo che ''a'' sia una radice primitiva per tutti i ''p''<sup>j</sup> con j<k. In particolare,
:<math>a^{\phi(p^{k-2})}\equiv 1 \mod p^{k-2}</math>
ovvero
:<math>a^{\phi(p^{k-2})}=1+lp^{k-2}</math>
per un qualche ''l''. Questa relazione vale anche modulo ''p''<sup>k</sup>; inoltre l'ordine di ''a'' modulo ''p''<sup>k</sup> deve essere un multiplo di <math>\phi(p^{k-1})</math>, perché ha quest'ordine modulo ''p''<sup>k-1</sup>. Quindi, poiché <math>\phi(p^k)=p\phi(p^{k-1})</math>, l'ordine può essere solo <math>\phi(p^{k-1})</math> o <math>p\phi(p^{k-1})</math>; in particolare, ''a'' è una radice primitiva se il suo ordine è il secondo di questi valori. Se p è un primo dispari,
:<math>a^{\phi(p^{k-1})}=(a^{\phi(p^{k-2})})^p=(1+lp^{k-2})^p\equiv 1+\binom{p}{p-1}lp^{k-2}\mod p^k\equiv 1+lp^{k-1}\mod p^k</math>
:<math>a^{\phi(p^{k-2})}=1+lp^{k-2},</math>
Questa quantità è uguale a 1 se e solo se ''l'' è divisibile per ''p''; tuttavia, se lo fosse, si avrebbe
per un qualche <math>l</math><math></math>. Questa relazione vale anche modulo <math>p^k</math>; inoltre l'ordine di <math>a</math> modulo <math>p^k</math> deve essere un multiplo di <math>\phi(p^{k-1})</math>, perché ha quest'ordine modulo <math>p^{k-1}</math>. Quindi, poiché <math>\phi(p^k)=p\phi(p^{k-1})</math>, l'ordine può essere solo <math>\phi(p^{k-1})</math> o <math>p\phi(p^{k-1})</math>; in particolare, <math>a</math> è una radice primitiva se il suo ordine è il secondo di questi valori. Se <math>p</math> è un primo dispari
:<math>a^{\phi(p^{k-1})}=(a^{\phi(p^{k-2})})^p=(1+lp^{k-2})^p\equiv 1+\binom{p}{p-1}lp^{k-2}\mod p^k\equiv 1+lp^{k-1}\mod p^k.</math>
Questa quantità è uguale a <math>1</math> se e solo se <math>l</math> è divisibile per <math>p</math>; tuttavia, se lo fosse, si avrebbe
:<math>a^{\phi(p^{k-2})}=1+lp^{k-2}\equiv 1\mod p^{k-1}</math>
contro l'ipotesi che l'ordine di ''<math>a''</math> modulo ''p''<supmath>p^{k-1}</supmath> sia <math>\phi(p^{k-1})</math>. Questo è assurdo, e quindi l'ordine di ''<math>a''</math> modulo ''p''<supmath>p^k</supmath> è esattamente <math>\phi(p^k)</math>, e ''<math>a''</math> è una radice primitiva modulo ''p''<supmath>p^k</supmath>. Per induzione questo è valido per ogni ''<math>k''</math>.
L'estensione ai numeri nella forma 2''p''<supmath>''2p^k''</supmath> segue immediatamente, perché il gruppo moltiplicativo di questo anello contiene lo stesso numero di elementi di quello dell'anello di ''p''<supmath>''p^k''</supmath> elementi, ed esiste una corrispondenza biunivoca che conserva le operazioni (ossia un [[isomorfismo]]) tra questi due gruppi.
== Funzioni simmetriche delle radici primitive modulo p ==
Indicando con <math>g</math> il generatore di <math>Z_p ^*</math> allora, per quanto precedentemente esposto, tutte le radici primitive modulo p si potranno esprimere come <math>g^i</math> dove <math>(i,\phi(p))=(i,p-1)=1</math> .
Indicando con <math>g</math> il generatore di <math>\Z_p^*</math> allora, per quanto precedentemente esposto, tutte le radici primitive modulo <math>p</math> si potranno esprimere come <math>g^i</math> dove <math>(i,\phi(p))=(i,p-1)=1</math> .
Gauss nelle Disquisitiones Arithmeticae dimostrò agli articoli 80 ed 81 il valore (modulo p primo) della somma delle radici primitive di <math>Z_p</math> e del loro prodotto.
Gauss nelle Disquisitiones Arithmeticae dimostrò agli articoli 80 ed 81 il valore (modulo <math>p</math> primo) della somma delle radici primitive di <math>\Z_p</math> e del loro prodotto.
Esse valgono:
* <math>\prod_{(i,p-1)=1} g^i \equiv 1 \pmod{p}</math> dove <math>p</math> primo diverso da <math>3</math>.(Art.80, DA)
* <math>\sum_{(i,p-1)=1} g^i \equiv \mu(p-1) \pmod{p}</math> per qualsiasi <math>p</math> primo, <math>\mu</math> è la [[funzione di Möbius]]. Ovviamente Gauss descrisse la funzione di Möbius, che non era stata ancora formalizzata al suo tempo, in maniera equivalente. (Art.81, DA)
La seconda identità si può estendere considerando tutti gli elementi di ordine <math>d</math>, con <math>d</math> divisore di <math>p-1</math>. Sia <math>h</math> un elemento di <math>\Z_p ^*</math> di ordine <math>d</math>, allora tutti gli elementi di ordine d saranno del tipo <math>h^j</math> con <math>(j,d)=1</math> e quindi saranno in numero <math>\phi(d)</math> . La loro somma vale <math>\sum_{(j,d)=1} h^j \equiv \mu(d) \pmod{p}</math>. Tramite tale formula possiamo calcolare la somma delle potenze k-esime delle radici primitive. Supponiamo che k sia tale che <math>(k,p-1)=1</math> allora tale elevamento a potenza k manda l'insieme delle radici primitive in sé stesso e pertanto <math>\sum_{(i,p-1)=1} (g^i)^k \equiv \mu(p-1) \pmod{p}</math>. Ora consideriamo un k che divida interamente p-1, se <math>g</math>
:<math>\sum_{(j,d)=1} h^j \equiv \mu(d) \pmod{p}.</math>
è radice primitiva (e quindi ha ordine p-1), l'elemento <math>g^k</math> avrà ordine pari a <math>\tfrac{p-1}{k}</math> quindi l'insieme delle radici primitive (ossia l'insieme degli elementi di ordine p-1) viene mandato nell'insieme degli elementi di ordine <math>\tfrac{p-1}{k}</math> che ha cardinalità <math>\phi(\tfrac{p-1}{k})</math> . Tale funzione è iniettiva se e solo se <math>k=1</math> mentre negli altri casi si assiste ad una "restrizione" delle radici primitive, nel senso che <math>\tfrac{\phi(p-1)}{\phi(\tfrac{p-1}{k})}</math> radici primitive vengono mandate nello stesso elemento di ordine <math>\tfrac{p-1}{k}</math> . Tale funzione è suriettiva, detto ciò per calcolare <math>\sum_{(i,p-1)=1} (g^i)^k</math> basta calcolare la sommatoria degli elementi di ordine <math>\tfrac{p-1}{k}</math> e moltiplicare tale valore per l' "indice di restrizione" <math>\tfrac{\phi(p-1)}{\phi(\tfrac{p-1}{k})}</math> . Quindi <math>\sum_{(i,p-1)=1} (g^i)^k=\tfrac{\phi(p-1)}{\phi(\tfrac{p-1}{k})}\mu(\tfrac{p-1}{k})</math>. Sia ora <math>k</math> dove <math>(k,p-1)=b</math>, quindi <math>k=ab</math> e <math>(a,p-1)=1</math> pertanto al posto di applicare direttamente la potenza <math>k</math> alle radici primitive, prima applichiamo la potenza <math>a</math> e poi,agli elementi ottenuti, la potenza <math>b</math>. La potenza <math>a</math> manda le radici primitive in sé stesse, la potenza <math>b</math> le fà "restringere" in un sottoordine e pertanto, indicando <math>(k,p-1)</math> in luogo di <math>b</math> otteniamo:
Tramite tale formula possiamo calcolare la somma delle potenze <math>k</math>-esime delle radici primitive. Supponiamo che <math>k</math> sia tale che <math>(k,p-1)=1</math> allora tale elevamento a potenza <math>k</math> manda l'insieme delle radici primitive in sé stesso e pertanto
<math>\sum_{(i,p-1)=1} (g^i)^k=\tfrac{\phi(p-1)}{\phi(\tfrac{p-1}{(k,p-1)})}\mu(\tfrac{p-1}{(k,p-1)})</math>
:<math>\sum_{(i,p-1)=1} (g^i)^k \equiv \mu(p-1) \pmod{p}.</math>
<nowiki> </nowiki>Tali formule si rivelano utili per calcolare le varie funzioni simmetriche delle radici primitive, tramite i teoremi newtoniani riusciamo facilmente nell'impresa. Supponiamo di voler calcolare il valore della sommatoria del prodotto delle radici primitive prese due a due, allora tramite i teoremi newtoniani otteniamo che:
Ora consideriamo un <math>k</math> che divida interamente <math>p-1</math>, se <math>g</math> è radice primitiva (e quindi ha ordine <math>p-1</math>), l'elemento <math>g^k</math> avrà ordine uguale a <math>\tfrac{p-1}{k}</math> quindi l'insieme delle radici primitive (ossia l'insieme degli elementi di ordine <math>p-1</math>) viene mandato nell'insieme degli elementi di ordine <math>\tfrac{p-1}{k}</math> che ha cardinalità <math>\phi(\tfrac{p-1}{k})</math>. Tale funzione è iniettiva se e solo se <math>k=1</math> mentre negli altri casi si assiste ad una "restrizione" delle radici primitive, nel senso che <math>\tfrac{\phi(p-1)}{\phi\left(\tfrac{p-1}{k}\right)}</math> radici primitive vengono mandate nello stesso elemento di ordine <math>\tfrac{p-1}{k}</math>. Tale funzione è suriettiva, detto ciò per calcolare
<math>\sum_{(ij,p-1)=1;i \ne j} g^ig^j \equiv \tfrac{1}{2}[(\sum_{(i,p-1)=1} g^i )^2-\sum_{(i,p-1)=1} (g^i)^2]\equiv \tfrac{1}{2}[(\mu(p-1))^2-\mu(\tfrac{p-1}{2})\tfrac{\phi(p-1)}{\phi(\tfrac{p-1}{2})}] \pmod{p} </math>
:<math>\sum_{(i,p-1)=1} (g^i)^k,</math>
Considerando ora il polinomio monico delle radici primitive modulo p (primo e diverso da 3) esso sarà di grado <math>\phi(\phi(p))=\phi (p-1)</math>:
basta calcolare la sommatoria degli elementi di ordine <math>\tfrac{p-1}{k}</math> e moltiplicare tale valore per l'"indice di restrizione" <math>\tfrac{\phi(p-1)}{\phi\left(\tfrac{p-1}{k}\right)}</math>. Quindi
<math>x^{\phi(p-1)} +A_{n-1} x^{\phi(p-1)-1}+...+A_1 x+A_0\equiv\prod_{(i,p-1)=1} (x-g^i) \pmod{p}</math>
:<math>\sum_{(i,p-1)=1} (g^i)^k=\tfrac{\phi(p-1)}{\phi\left(\tfrac{p-1}{k}\right)}\mu(\tfrac{p-1}{k}).</math>
Si dimostra che valgono le relazioni <math>A_i =A_{\phi(p-1)-i}</math> . Infatti se <math>y</math> è una radice primitiva allora anche <math>y^{-1}</math> la è e tali radici sono distinte per p diverso da tre. Valutando i polinomi in queste radici otteniamo:
Sia ora <math>k</math> dove <math>(k,p-1)=b</math>, quindi <math>k=ab</math> e <math>(a,p-1)=1</math> pertanto al posto di applicare direttamente la potenza <math>k</math> alle radici primitive, prima applichiamo la potenza <math>a</math> e poi,agli elementi ottenuti, la potenza <math>b</math>. La potenza <math>a</math> manda le radici primitive in sé stesse, la potenza <math>b</math> le fa "restringere" in un sottoordine e pertanto, indicando <math>(k,p-1)</math> in luogo di <math>b</math> otteniamo:
(1) <math>y^{\phi(p-1)} +A_{n-1} y^{\phi(p-1)-1}+...+A_1 y+A_0\equiv 0 \pmod{p}</math>
(2) :<math>({\tfracsum_{(i,p-1)=1}{y}} (g^i)^k=\tfrac{\phi(p-1)} +A_{n-1} \phi\left({\tfrac{p-1}{y}})^{\phi(k,p-1)-1}+...+A_1 \right)}\mu({\tfrac{p-1}{y}(k,p-1)})+A_0\equiv 0 \pmod{p}.</math>
Tali formule si rivelano utili per calcolare le varie funzioni simmetriche delle radici primitive, tramite i teoremi newtoniani riusciamo facilmente nell'impresa. Supponiamo di voler calcolare il valore della sommatoria del prodotto delle radici primitive prese due a due, allora tramite i teoremi newtoniani otteniamo che:
:<math>\sum_{(ij,p-1)=1;i \ne j} g^ig^j \equiv \tfrac{1}{2}[(\sum_{(i,p-1)=1} g^i )^2-\sum_{(i,p-1)=1} (g^i)^2]\equiv \tfrac{1}{2}[(\mu(p-1))^2-\mu(\tfrac{p-1}{2})\tfrac{\phi(p-1)}{\phi\left(\tfrac{p-1}{2}\right)}] \pmod{p}.</math>
Considerando ora il polinomio monico delle radici primitive modulo <math>p</math> (primo e diverso da <math>3</math>) esso sarà di grado <math>\phi(\phi(p))=\phi (p-1)</math>:
:<math>x^{\phi(p-1)} +A_{n-1} x^{\phi(p-1)-1}+\ldots+A_1 x+A_0\equiv\prod_{(i,p-1)=1} (x-g^i) \pmod{p}.</math>
Si dimostra che valgono le relazioni <math>A_i =A_{\phi(p-1)-i}</math>. Infatti se <math>y</math> è una radice primitiva allora anche <math>y^{-1}</math> lo è, e tali radici sono distinte per <math>p</math> diverso da <math>3</math>. Valutando i polinomi in queste radici otteniamo:
(1) <math>y^{\phi(p-1)} +A_{n-1} y^{\phi(p-1)-1}+\ldots+A_1 y+A_0\equiv 0 \pmod{p}</math>
(2) <math>({\tfrac{1}{y}})^{\phi(p-1)} +A_{n-1} ({\tfrac{1}{y}})^{\phi(p-1)-1}+\ldots+A_1 ({\tfrac{1}{y}})+A_0\equiv 0 \pmod{p}</math>
moltiplicando la (2) per <math>({\tfrac{1}{y}})^{\phi(p-1)}</math> otteniamo:
(2) <math>A_0 y^{\phi(p-1)} +A_1 y^{\phi(p-1)-1}+...\ldots+A_{n-1} y+1\equiv 0 \pmod{p}</math> Sottraendo la (1) alla (2') otteniamo:
(3) <math>(A_0 -1) y^{\phi(p-1)} +(A_1 -A_{n-1}) y^{\phi(p-1)-1}+...\ldots+(A_{n-1}- A_1) y+(1- A_0)\equiv 0 \pmod{p}</math>
In particolare il termine <math>A_0</math> vale <math>(-1)^{\phi(p-1)}\prod_{(i,p-1)=1} g^i </math> dove p diverso da tre, pertanto per qualsiasi <math>p</math> primo e maggiore di <math>3</math> si ha che <math>\phi(p-1)</math> è pari e quindi <math>A_0 \equiv 1 \pmod{p}</math>. Sostituendo tale valore nella (3) otteniamo che l'equazione ha, quindi, grado <math>\phi(p-1)-1</math> e della quale due radici sono <math>y</math> e <math>y^{-1}</math>; considerando le altre radici primitive a due a due, l'una l'inverso dell'altra, otteniamo sempre la stessa equazione (3) e quindi, in sintesi, la (3) si annulla per tutte le <math>\phi(p-1)</math> radici primitive ed ha grado <math>\phi(p-1)-1</math> . Ma allora è identicamente nulla e quindi <math>A_i =A_{\phi(p-1)-i}</math> .
Allora in base alle considerazioni precedenti sappiamo:
<math>x^{\phi(p-1)} -\mu(p-1)x^{\phi(p-1)-1}+...\ldots-\mu(p-1)x+1\equiv\prod_{(i,p-1)=1} (x-g^i) \pmod{p}.</math>
Riportiamo alcuni esempi di tali polinomi:
* <math>x+1 \equiv 0 \pmod{3}</math> (Perper questo non si può impiegare l'Art.80 di Gauss, ma si è solo verificato "a mano")
* <math>x^2+1 \equiv 0 \pmod{5}</math>
* <math>x^2-x+1 \equiv 0 \pmod{7}</math>
* <math>x^{12}-x^{10}+x^8-x^6+x^4-x^2+1 \equiv 0 \pmod{29}</math>
* <math>x^8+x^7-x^5-x^4-x^3+x+1 \equiv0 \pmod{31}</math>
Nei moduli p laddoveLaddove nel polinomio si assiste ad un "passo" costante tra gli esponenti di <math>x</math> (per esempio per <math>p=5</math> il passo degli esponenti è <math>2</math>, come succede anche per <math>p=13,29</math>) e nominando <math>k</math> il valore di tale "passo", allora in tali moduli l'insieme delle radici primitive è quozientabile tramite il gruppo delle radici <math>k</math>-esime dell'unità , e vale il viceversa.
In particolare se <math>p</math> è un [[numero primo di Fermat]] allora il polinomio delle sue radici primitive sarà:
:<math>x^{\tfrac{p-1}{2}}+1 \equiv0 \pmod{p}.</math>
Infatti se <math>p</math> è un primo di Fermat esso è del tipo <math>p=2^{2^{n}}+1</math> ed il numero delle radici primitive sarà
:<math>\phi(\phi(p))=\phi(p-1)=\phi(2^{2^{n}})=2^{2^{n}-1},</math>
tale sarà anche il grado del polinomio delle radici primitive. Per il [[piccolo teorema di Fermat]] l'equazione che ha per radici tutti degli elementi di <math>\Z_p ^*</math> è
In particolare se p è un primo di Fermat allora il polinomio delle sue radici primitive sarà: <math>x^{p-1}-1\equiv(x^{\tfrac{p-1}{2}}-1)(x^{\tfrac{p-1}{2}}+1) \equiv0equiv 0 \pmod{p},</math>.
Infatti se p è un primo di Fermat esso è del tipo: <math>p=2^{2^{n}}+1</math> ed il numero delle radici primitive sarà <math>\phi(\phi(p))=\phi(p-1)=\phi(2^{2^{n}})=2^{2^{n}-1}</math> , tale sarà anche il grado del polinomio delle radici primitive. Per il Piccolo teorema di Fermat l'equazione che ha per radici tutti degli elementi di <math>Z_p ^*</math> è <math>x^{p-1}-1\equiv(x^{\tfrac{p-1}{2}}-1)(x^{\tfrac{p-1}{2}}+1) \equiv 0 \pmod{p}</math> dove il primo polinomio si annulla solo e solamente per i residui quadratici modulo <math>p</math> (Criteriocriterio di Eulero) e poiché le radici primitive non sono residui quadratici, il polinomio delle radici primitive deve fattorizzare il secondo polinomio. Quest'ultimo è monico e di grado <math>\tfrac{p-1}{2}=2^{2^{n}-1}</math>, cioè ha lo stesso grado del polinomo cercato: pertanto lo è.
==Note==
| 