Radice primitiva modulo n: differenze tra le versioni

Versione delle 02:52, 4 ott 2014

Versione delle 02:59, 4 ott 2014

Riga 77:

* <math>\prod_{(i,p-1)=1} g^i \equiv 1 \pmod{p}</math> dove p primo diverso da 3.(Art.80, DA)

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