Aritmetica modulare/Congruenze lineari: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m cambio avanzamento a 100% |
calcola funzione eulero |
||
Riga 108:
:<math>\phi\left(ab\right)=\phi(a)\phi(b)</math>
per ogni coppia di ''a'' e ''b'' coprimi.
A partire da questo è facile calcolare il valore di <math>\phi\left(n\right)</math> per ogni ''n'': infatti questo può essere scomposto nel prodotto
:<math>n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}</math>
dove i <math>p_k</math> sono primi e diversi tra loro. A questo punto resta da calcolare solamente <math>\phi\left(p^a\right)</math>: ma questo è facile, perché gli unici numeri minori di <math>p^a</math> e non coprimi con esso sono i multipli di ''p'', e questi sono in numero di <math>p^{a-1}</math>; quindi <math>\phi\left(p^a\right)=p^a-p^{a-1}=p^{a-1}(p-1)</math>.
A questo punto si ottiene
:<math>\phi(n)=p_1^{a_1-1}(p_1-1)p_2^{a_2-1}(p_2-1)\cdots p_1^{a_k-1}(p_k-1)</math>
o, in forma più elegante,
:<math>\phi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_k}\right)</math>
== Il lemma di Thue ==
| |||