Radice primitiva modulo n: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
fix incipit |
Funzionalità collegamenti suggeriti: 3 collegamenti inseriti. Etichette: Modifica visuale Modifica da mobile Modifica da web per mobile Attività per i nuovi utenti Suggerito: aggiungi collegamenti |
||
Riga 68:
contro l'ipotesi che l'ordine di <math>a</math> modulo <math>p^{k-1}</math> sia <math>\phi(p^{k-1})</math>. Questo è assurdo, e quindi l'ordine di <math>a</math> modulo <math>p^k</math> è esattamente <math>\phi(p^k)</math>, e <math>a</math> è una radice primitiva modulo <math>p^k</math>. Per induzione questo è valido per ogni <math>k</math>.
L'estensione ai numeri nella forma <math>2p^k</math> segue immediatamente, perché il gruppo moltiplicativo di questo anello contiene lo stesso numero di elementi di quello dell'anello di <math>p^k</math> elementi, ed esiste una [[corrispondenza biunivoca]] che conserva le operazioni (ossia un [[isomorfismo]]) tra questi due gruppi.
== Funzioni simmetriche delle radici primitive modulo p ==
Riga 103:
:<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>
Riga 154:
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 polinomo 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:
|