Radice primitiva modulo n: differenze tra le versioni

Versione delle 12:14, 17 ott 2014

Versione delle 01:01, 19 ott 2014

Riga 150:

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