Aritmetica modulare/Radici primitive: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
→Indici: correzione |
m typo |
||
Riga 5:
Dal piccolo teorema di Fermat sappiamo che per ogni ''x'' ed ''n'' (con ''x'' ed ''n'' coprimi) si ha
:<math>x^{\phi(n)}\equiv 1\mod n</math>
Può tuttavia esistere un numero <math>h<\phi(n)</math> tale che
:<math>x^h\equiv 1\mod n</math>
Se ''h'' è il minore intero possibile con questa caratteristica, si dice che ''h'' è l''''ordine''' di ''x'' modulo ''n''; se in particolare <math>h=\phi(n)</math>, allora si dice che ''x'' è una '''radice primitiva''' modulo ''n''. Ad esempio 5 ha la radice primitiva 2, perché
Riga 23:
e quindi ''k'' dovrebbe essere l'ordine di ''x'', essendo minore di ''h''. Questo è assurdo, e ''h'' divide ''N''.
Supponiamo ora che ''x'' e ''y'' abbiamo ordine rispettivamente ''h'' e ''k'', e che ''h'' e ''k'' siano coprimi. Allora ''xy'' ha ordine ''hk''. È infatti ovvio, da quanto detto prima, che ne è un divisore
:<math>(xy)^{hk}=(x^h)^k (y^k)^h\equiv 1^k 1^h\mod n\equiv 1\mod n</math>
Supponiamo ora che l'ordine di ''xy'' sia ''HK'', dove ''H'' divide ''h'' e ''K'' divide ''k''; ''H'' e ''K'' sono coprimi, essendo i loro multipli. Supponiamo ''h'' = ''Hj''; elevando ''xy'' alla ''HjK'', si ha
Riga 52:
Consideriamo il polinomio <math>P(x)=x^{p-1}-1</math>: per il piccolo teorema, ha esattamente ''p'' -1 zeri distinti (cioè tutti gli elementi di <math>\mathbb{Z}_p</math> eccetto lo zero), e poniamo <math>q_i=q,~a_i=a</math>. Si ha <math>p-1=q^aw</math> per un ''m''; ponendo <math>x^{q^a}=y</math>, risulta evidente che
:<math>x^{p-1}-1=y^w-1=(y-1)(y^{w-1}+y^{w-2}+\cdots+y^1+1)
In ''x'', i due polinomi a destra hanno grado rispettivamente <math>q^a</math> e <math>p-1-q^a</math>, e quindi, poiché ''p'' è primo, hanno al massimo rispettivamente <math>q^a</math> e <math>p-1-q^a</math> soluzioni. Ma la somma del loro numero di soluzioni deve dare ''p'' -1, quindi ne hanno esattamente tante. Ma ora la congruenza
:<math>x^{q^{a-1}}\equiv 1\mod p</math>
| |||