Aritmetica modulare/Radici primitive: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
indici |
m typo |
||
Riga 17:
Da ora in poi supporremo sempre ''n'' fissato e ''x'' coprimo con ''n'', e porremo <math>N=\phi(n)</math>.
Supponiamo che ''x'' abbia ordine ''h''. Una prima proprietà, banale, è che ''h'' è un divisore di ''N''.
:<math>hy\equiv k\mod N</math>
è risolubile per un ''y'' >1. Quindi
Riga 85:
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
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.
| |||