Radice primitiva modulo n: differenze tra le versioni

Versione delle 02:47, 4 ott 2014

Versione delle 02:48, 4 ott 2014

Riga 78:

* <math>\sum_{(i,p-1)=1} g^i \equiv \mu(p-1) \pmod{p}</math> per qualsiasi p 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 d con d divisore di p-1. Sia <math>h</math> un elemento di <math>Z_p ^*</math> di ordine d, 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>

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

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

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

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

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

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

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:

(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>({\tfrac{1}{y}})^{\phi(p-1)} +A_{n-1} ({\tfrac{1}{y}})^{\phi(p-1)-1}+...+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}+...+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}+...+(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 p primo e maggiore di 3 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> .

In base alle considerazioni precedenti sappiamo:

<math>x^{\phi(p-1)} -\mu(p-1)x^{\phi(p-1)-1}+...-\mu(p-1)x+1\equiv\prod_{(i,p-1)=1} (x-g^i) \pmod{p}</math>

Riportiamo alcuni esempi di tali polinomi: