Aritmetica modulare/Radici primitive: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m cambio avanzamento a 100% |
finito... |
||
Riga 31:
e quindi ''hK'' è un multiplo di ''k''; essendo ''h'' coprimo con ''k'', si deve avere che ''K'' è un multiplo di ''k'', e quindi, essendone anche un divisore, ''k'' = ''K''. Allo stesso modo ''h'' = ''H'', e l'ordine di ''xy'' è ''hk''.
Consideriamo ora il caso dell'ordine di un numero ''x'' rispetto a due moduli coprimi ''n'' ed ''m''. Sia ''h'' l'ordine di ''x'' rispetto ad ''n'' e ''k'' l'ordine di ''x'' rispetto a ''m''. Allora l'ordine di ''x'' rispetto a ''nm'' è il minimo comune multiplo tra ''h'' e ''k''. Infatti, dire che
:<math>x^l\equiv 1\mod nm</math>
equivale a dire
:<math>\begin{cases} x^l\equiv 1 \mod n\\ x^l\equiv 1\mod m\end{cases}</math>
e questo è possibile solo se ''l'' è multiplo sia di ''h'' che di ''k'', e in particolare vale per ogni multiplo comune di ''h'' e di ''k'': quindi il loro multiplo comune più piccolo, cioè il loro m.c.m., è l'ordine di ''x'' rispetto a ''nm''.
== Numeri primi ==
Line 50 ⟶ 56:
:<math>x^{q^{a-1}}\equiv 1\mod p</math>
ha al massimo <math>q^{a-1}</math> soluzioni, che sono di meno di <math>q^a</math>; quindi esattamente <math>q^a-q^{a-1}</math> elementi di <math>\mathbb{Z}_p</math> hanno ordine <math>q^a</math>. Poiché questo avviene per ogni ''i'', per quanto detto prima, esiste un elemento che ha ordine <math>q_1^{a_1}q_2^{a_2}\cdots q_s^{a_s}=p-1</math>, cioè una radice primitiva.
== Potenze dei numeri primi ==
Esaminiamo ora il caso delle potenze dei numeri primi, e consideriamo il caso ''p'' =2. Per ''n'' =4, 3 è una radice primitiva. L'esempio all'inizio del capitolo mostra invece che 8 non ha una radice primitiva, perché <math>a^2\equiv 1\mod 8</math> per ogni ''a'' dispari; questo implica che per ogni altra potenza di due non può esserci una radice primitiva: infatti supponiamo che questo avvenga per un <math>2^k</math>, e che ''a'' sia la radice primitiva, tale che ''a'' è congruo a ''b'' modulo 8 (questa congruenza su una congruenza ha senso, perché <math>2^k</math> è, per ipotesi, multiplo di 8). Allora le potenze di ''a'' sono congrue, modulo 8, alternativamente a ''b'' e ad 1, mentre dovrebbero essere congrue anche alle altre due (se ''b'' =3, ad esempio, dovrebbero essere congrue anche a 5 e a 7); quindi una radice primitiva non può esistere.
Sia ora ''p'' un primo maggiore di 2, e ''a'' una sua radice primitiva. <math>\phi(p^2)=p(p-1)</math>; inoltre, l'ordine di ''a'' modulo <math>p^2</math> è un multiplo di ''p'' -1, perché per avere
:<math>a^k\equiv 1\mod p^2</math>
si deve avere
:<math>a^k\equiv 1\mod p</math>
Gli unici multipli di ''p'' -1 che dividono ''p'' (''p'' -1) sono i due estremi, cioè gli stessi ''p'' -1 e ''p'' (''p'' -1): se è quest'ultimo, allora ''a'' è una radice primitiva modulo <math>p^2</math>; supponiamo invece che non lo sia, e consideriamo il numero (coprimo con ''p'') ''p'' - ''a''. Attraverso lo sviluppo del binomio di Newton si ha
:<math>(p-a)^{p-1}=\sum_{i=0}^{p-1} \binom{p-1}{i} (-1)^i a^i p^{p-1-i}</math>
Modulo <math>p^2</math>, gli unici elementi che restano sono quelli con ''i'' =''p'' -2 e ''i'' =''p'' -1:
:<math>(p-a)^{p-1}\equiv \binom{p-1}{p-2} (-1)^{p-2} a^{p-2} p+\binom{p-1}{p-1} (-1)^{p-1} a^{p-1}\mod p^2\equiv (p-1)(-1)a^{-1}p+1\mod p^2\equiv pa^{-1}+1\mod p^2</math>
che è congruo a 1 modulo <math>p^2</math> se e solo se
:<math>pa^{-1}\equiv 0\mod p^2\iff a^{-1}\equiv 0\mod p</math>
che è impossibile perché ''a'' è coprimo con ''p'', essendone una radice primitiva. Quindi o ''a'' o ''p'' - ''a'' è una radice primitiva per <math>p^2</math>, o, detto in altri termini, questa esiste sempre.
Dimostreremo ora che, se ''a'' è una radice primitiva per <math>p^2</math>, allora è una radice primitiva anche per <math>p^k</math> per ogni ''k'' >2. Procediamo per induzione: se ''k'' =2 questo è vero per ipotesi (abbiamo dimostrato prima che ''a'' esiste) e inoltre ''a'' è una radice primitiva modulo ''p''. Supponiamo che il teorema sia valido per ogni ''k'' fino a ''K'' escluso. In questo caso l'ordine di ''a'' può essere solamente <math>\phi(p^{K-1})=p^{K-2}(p-1)</math> oppure <math>\phi(p^K)=p^{K-1}(p-1)</math>. Inoltre abbiamo
:<math>a^{\phi(p^{K-2})}=1+lp^{K-2}</math>
Elevando ''a'' alla <math>\phi(p^{K-1})</math> si ha
:<math>a^{\phi(p^{K-1})}=a^{p^{K-2}(p-1)}=(a^{p^{K-3}(p-1)})^p=(a^{\phi(p^{K-2})})^p=(1+lp^{K-2})^p=\binom{p}{0} p^0+\binom{p}{1} lp^{K-2}+\binom{p}{2} l^2p^{2(K-2)}+\cdots</math>
e calcolando modulo <math>p^K</math>
:<math>a^{\phi(p^{K-1})}\equiv 1+lpp^{K-2}\mod p^K\equiv 1+lp^{K-1}\mod p^K</math>
Se ora ''l'' non è divisibile per ''p'', abbiamo dimostrato che ''a'' è una radice primitiva modulo <math>p^K</math>; se invece ''a'' è divisible per ''p'' si ha
:<math>a^{\phi(p^{K-2})}=1+l_1pp^{K-2}\equiv 1\mod p^{K-1}</math>
e quindi ''a'' ha ordine <math>\phi(p^{K-2})</math> modulo <math>p^{K-1}</math>, contro l'ipotesi che ''a'' sia una radice primitiva, questo è assurdo, e quindi ''a'' è una radice primitiva modulo <math>p^K</math>. Per induzione, segue che ''a'' è una radice primitiva per ogni <math>p^k</math>, ''k'' >2.
== Numeri divisibile da più di un primo ==
Consideriamo ora un numero ''n'' che non è potenza di un numero primo, fattorizzandolo come <math>n=p_1^{a^1}p_2^{a_2}\cdots p_s^{a_s}</math>. La funzione di Eulero è moltiplicativa, quindi l'ordine necessario per essere una radice primitiva è <math>\phi(p_1^{a^1})\phi(p_2^{a_2})\cdots \phi(p_k^{a_k})</math>; se ''x'' non è una radice primitiva modulo <math>p^a</math> (qualunque ''p''), a maggior ragione non lo potrà essere modulo ''n'', perché vi sono degli elementi modulo <math>p^a</math> che non genera (sia ''b'' uno di questi): se <math>x^k</math> non è mai congruo a ''b'' modulo <math>p^a</math>, non lo potrà mai essere modulo ''n'', e quindi ''x'' non è una radice primitiva.
Consideriamo ora un ''x'' che è una radice primitiva modulo <math>p_i^{a_i}</math> per ogni ''i''. Questa esiste, perché di ognuna esistono le radici primitive <math>x_1,x_2,\ldots,x_s</math>, e a questa ''s''-upla è possibile assegnare un elemento di <math>\mathbb{Z}_n</math> (vedi il capitolo sulle [[Aritmetica modulare/Congruenze lineari|congruenze lineari]]). Affinché il suo ordine modulo ''n'' sia il prodotto degli ordini, questi devono essere tutti coprimi tra loro. Tuttavia, se ''p'' è un primo dispari, <math>\phi\left(p\right)=p-1</math> è pari, e così la funzione di Eulero delle sue potenze. Anche <math>\phi\left(2^k\right)</math>, per ''k'' >1, è pari: quindi, per avere una radice primitiva, ''n'' può contenere nella sua fattorizzazione al massimo un primo dispari (eventualmente elevato a qualche potenza) e 2.
Ricapitolando, gli unici ''n'' che hanno una radice primitiva sono:
*2 e 4;
*<math>p^k</math> per ''p'' primo dispari e ''k'' qualsiasi;
*<math>2p^k</math> per ''p'' primo dispari e ''k'' qualsiasi.
[[categoria:Aritmetica modulare]]
| |||