Radice primitiva modulo n: differenze tra le versioni

Versione delle 02:45, 4 ott 2014

Versione attuale delle 16:19, 17 giu 2023

(39 versioni intermedie di 16 utenti non mostrate)

Riga 1:

In [[aritmetica modulare]], ununa '''generatoreradice primitiva modulo <math>n</math>''' èo un'''generatore interomodulo <math>n</math>''g' (o semplicemente '''generatore''') è un [[numero intero]] le cui potenze '''(mod[[Aritmetica modulare|modulo]] <math>n)'''</math> sono congruenti con i numeri [[coprimo|coprimi]] ad ''<math>n''</math>.

Un '''generatore''' o '''radice primitiva modulo ''n''''' è un concetto dell'[[aritmetica modulare]], in [[teoria dei numeri]]. Se ''<math>n''&\ge; 1</math> è un [[numeroNumero intero|intero]], i numeri [[coprimo|coprimi]] ad ''<math>n''</math>, considerati modulo ''<math>n''</math>, costituiscono un [[gruppoGruppo (matematica)|gruppo]] rispetto all'operazione di moltiplicazione; esso viene generalmente indicato con <math>('''\Z'''/''n'''''\Z''')<sup>&times;^*</supmath> oppure '''Z'''_n<supmath>\Z_n^*</supmath>. Esso è un [[gruppo ciclico]] se e solo se ''<math>n''</math> è uguale a <math>2</math>, <math>4</math>, ''p''<supmath>''p^k''</supmath> o 2 ''p''<supmath>''2p^k''</supmath> per un [[numero primo]] [[numeroNumero dispari|dispari]] ''<math>p''</math> e ''<math>k'' &\ge; 1</math>. Un generatore di questo gruppo ciclico è chiamato '''radice primitiva modulo ''n''''', o anche '''elemento primitivo di Z'''_n<supmath>\Z_n^*</supmath>. 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''.

Si consideri per esempio ''<math>n'' = 14</math>. Gli elementi di

:<math>('''\Z'''/14'''\Z''')<sup>&times;^*,</supmath>

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> che sono [[coprimo|coprimi]] con <math>n = 14.</math>

sono le classi di congruenza di

Si ha che <math>3</math> è un generatore modulo <math>14</math>, perché 3² mod 14 = 9, 3³ mod 14 = 13, 3⁴ mod 14 = 11, 3⁵ mod 14 = 5 e 3⁶ mod 14 = 1. L'unica altra radice primitiva modulo <math>14</math> è <math>5</math>.

:1, 3, 5, 9, 11 e 13.

I generatori modulo <math>n</math> rivestono un'importanza considerevole in [[crittografia]].

3 è un generatore modulo 14, perché 3² = 9, 3³ = 13, 3⁴ = 11, 3⁵ = 5 e 3⁶ = 1 (modulo 14). L'unica altra radice primitiva modulo 14 è 5.

==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''

Riga 23:

|}

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|&phi;<math>(''\Z/n''\Z)]]^*</math>, (l'ordinecioè dia '''Z'''/''<math>\phi(n'''''Z''')<sup/math>&times;, 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 &phi;(''n''). Quindi determinare i diversi fattori primi di &phi;(''n''), siano ''p''₁,...,''p''_''k''. Ora, per ogni elemento ''m'' di ('''Z'''/''n'''''Z''')^&times;, 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.

:&phi;(&phi;(''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 &phi;(''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 &epsilon;>0 esistono delle costanti positive ''C'' e ''p''₀ tali che, per ogni [[numero primo|primo]] ''p'' &ge; ''p''₀, 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''^{1/4+&epsilon;}.

== Dimostrazione dell'esistenza di un generatore modulo ''p''^k, ''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

:<math>a^{p-1}\equiv 1\mod p,</math>

:70 ([[logaritmo naturale|ln]](''p''))².

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]]

I generatori modulo ''m'' rivestono un'importanza considerevole in [[crittografia]].

:<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>

== Dimostrazione dell'esistenza di un generatore modulo ''p''^k, p dispari==

che non può essere <math>1</math>, perché altrimenti <math>p</math> dividerebbe <math>a^{p-2}</math>, 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 <math>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''², 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''² 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''²; 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>

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

che non può essere 1, perché altrimenti ''p'' dividerebbe ''a''^''p''-2, il che è assurdo, e quindi l'ordine di ''p''+''a'' non è ''p''-1, e deve essere ''p''(''p''-1), cioè abbiamo trovato una radice primitiva modulo ''p''².

:<math>a^{\phi(p^{k-2})}\equiv 1 \mod p^{k-2},</math>

Per dimostrare la proposizione per ''p''^k, con ''k''>2, si procede per [[induzione]]: supponiamo che ''a'' sia una radice primitiva per tutti i ''p''^j con j<k. In particolare,

:<math>a^{\phi(p^{k-2})}\equiv 1 \mod p^{k-2}</math>

ossia

ovvero

:<math>a^{\phi(p^{k-2})}=1+lp^{k-2}</math>

:<math>a^{\phi(p^{k-2})}=1+lp^{k-2},</math>

per un qualche ''l''. Questa relazione vale anche modulo ''p''^k; inoltre l'ordine di ''a'' modulo ''p''^k deve essere un multiplo di <math>\phi(p^{k-1})</math>, perché ha quest'ordine modulo ''p''^k-1. 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>

per un qualche <math>l</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

Questa quantità è uguale a 1 se e solo se ''l'' è divisibile per ''p''; 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 <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 <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><math>\sum_{(j,d)=1} h^j \equiv \mu(d) \pmod{p}</math><math>\sum_{(j,d)=1} h^j \equiv\mu(d) \pmod{p}.</math>

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 \equiv \mu(p-1) \pmod{p}.</math>

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_{(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\left(\tfrac{p-1}{k}\right)}</math>. Quindi

:<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>

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 sottordine e pertanto, indicando <math>(k,p-1)</math> in luogo di <math>b</math> otteniamo:

:<math>\sum_{(i,p-1)=1} (g^i)^k=\tfrac{\phi(p-1)}{\phi\left(\tfrac{p-1}{(k,p-1)}\right)}\mu(\tfrac{p-1}{(k,p-1)}).</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>

Riga 90 ⟶ 133:

* <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>

Si vede che tali polinomi altro non sono che i polinomi ciclotomici <math>\Phi_n(x)</math> dove <math>n=p-1</math> con <math>p</math> numero primo.

Nei moduli p laddove nel polinomio si assiste ad un "passo" costante tra gli esponenti di x (per esempio per p=5 il passo degli esponenti è 2, come succede per p=13,29) e nominando k il valore di tale "passo", allora in tali moduli l'insieme delle radici primitive è quozientabile tramite il gruppo delle radici k-esime dell'unità , e vale il viceversa.

Laddove 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 p è un primo di Fermat allora il polinomio delle sue radici primitive sarà: <math>x^{\tfrac{p-1}{2}}+1 \equiv0 \pmod{p}</math>.

In particolare se <math>p</math> è un [[numero primo di Fermat]] allora il polinomio delle sue radici primitive sarà:

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 p (Criterio 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 è.

:<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> è

:<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>. [[Criterio di Eulero]]. 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 polinomio cercato: pertanto lo è.

Se <math>p</math> è un [[numero primo sicuro]] maggiore di <math>5</math>, ossia se <math>p=2q+1</math> dove <math>q</math> è un [[primo di Sophie Germain]] maggiore di <math>2</math>, il polinomio delle radici primitive ha coefficienti di valori alternativamente <math>+1</math> e <math>-1</math>. Infatti in tal caso si ha che la cardinalità di <math>\Z_p^*</math> è <math>2q</math> e pertanto gli elementi di <math>\Z_p^*</math> possono avere ordine solo di <math>2q,q,2,1</math>. Per l'ordine <math>1</math> abbiamo solo l'elemento <math>+1</math>, mentre per l'ordine <math>2</math> abbiamo solo l'elemento <math>-1</math>. Gli elementi di ordine <math>2q</math> sono equinumerosi agli elementi di ordine <math>q</math>, infatti <math>\phi(2q)=\phi(q)=q-1</math>. Sia <math>h</math> un elemento di ordine <math>q</math> allora, poiché <math>q</math> è coprimo con <math>2</math>, l'elemento <math>-h</math> ha ordine pari al [[minimo comune multiplo]] tra l'ordine di <math>-1</math> (che è <math>2</math>) e quello di <math>h</math> (che è <math>q</math>). In sintesi per ogni elemento <math>h</math> di ordine <math>q</math> abbiamo che l'elemento <math>-h</math> ha ordine <math>2q</math>.

Sia il polinomio delle radici di ordine <math>q</math> il seguente:

:<math>p_q(x)=x^{q-1}+M_{q-2}x^{q-2}\ldots+M_2x^2+M_1x+M_0,</math>

ma allora il polinomio delle radici di ordine <math>2q</math> (radici primitive) sarà:

:<math>p_{2q}(x)=x^{q-1}-M_{q-2}x^{q-2}\ldots+M_2x^2-M_1x+M_0,</math>

in quanto ogni coefficiente di <math>p_{2q}(x)</math> è somma di prodotti di <math>s</math> radici opposte a quelle di <math>p_q(x)</math>, quindi il segno dipende dalla parità di <math>s</math> .

Per quanto appena affermato, proponiamoci di determinare il polinomio delle radici di ordine <math>q</math> al fine di determinare quello di ordine <math>2q</math>. Sia <math>h</math> un elemento di ordine <math>q</math> allora tutti gli altri elementi di pari ordine si esprimeranno come <math>h^i</math> con <math>(i,q)=1</math> e <math>q</math>, ricordiamo, è numero primo maggiore di <math>2</math>. Esse saranno pertanto <math>h^1,h^2,h^3,\ldots,h^{q-1}</math> e se ad esse aggiungiamo l'elemento <math>1</math> allora sappiamo che esse sono le radici dell'equazione

:<math>x^q -1 \equiv 0 \pmod{p},</math>

che sappiamo fattorizzare in:

:<math>x^q -1 \equiv (x-1)(x^{q-1}+x^{q-2}+\ldots+x^2+x+1) \pmod{p},</math>

è immediato rilevare che

:<math>p_q(x) \equiv x^{q-1}+x^{q-2}+\ldots+x^2+x+1 \pmod{p},</math>

e per quanto detto prima otteniamo:

:<math>p_{2q}(x) \equiv x^{q-1}-x^{q-2}+\ldots+x^2-x+1 \pmod{p},</math>

che è il polinomio delle radici primitive.

==Note==

Riga 102 ⟶ 187:

* [[Tom M. Apostol]] (1976): Introduction to Analytic Number Theory, Springer-Verlag, New York. ISBN 0-387-90163-9 (Capitolo 10).

== Voci correlate ==

*[[Congettura di Artin]]

== Collegamenti esterni ==

*{{Collegamenti esterni}}

{{Portale|matematica}}

[[Categoria:Aritmetica modulare]]