Aritmetica modulare/Congruenze lineari: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m →Il lemma di Thue: typo |
applicazione alla funzione di eulero |
||
Riga 95:
:<math>\begin{cases} f(x)\equiv 0\mod n_1\\ f(x)\equiv 0\mod n_2 \\ \vdots \\ f(x)\equiv 0\mod n_k\end{cases}</math>
dove i vari moduli sono a due a due coprimi, e <math>\rho(n_i)</math> indica il numero di soluzioni della congruenza modulo <math>n_i</math>, allora <math>\rho(n)=\rho(n_1)\rho(n_2)\cdots\rho(n_k)</math> perché ogni possibile gruppo di soluzioni nei diversi moduli genera una diversa soluzione modulo ''n''.
== Un'applicazione: la funzione di Eulero ==
A partire da queste considerazioni si può provare che la funzione di Eulero è ''moltiplicativa'', cioè per ogni ''a'' e ''b'' coprimi si ha
:<math>\phi\left(ab\right)=\phi(a)\phi(b)</math>
Il punto di partenza è la considerazione che un numero ''n'' è coprimo con un prodotto ''ab'' se e solo se è coprimo sia con ''a'' che con ''b''. Infatti, se i fattori di ''n'' sono distinti da quelli di ''ab'', saranno a maggior ragione diversi sia da quelli di ''a'' che da quelli di ''b'', viceversa, se i fattori di ''n'' non compaiono né nella fattorizzazione di ''a'' né in quella di ''b'', non potranno essere in quella di ''ab''.
Consideriamo ora un <math>x\in\mathbb{Z}_{ab}</math>: per quanto abbiamo detto prima, lo possiamo identificare come una coppia <math>y\in\mathbb{Z}_a,~ z\in\mathbb{Z}_b</math>, e si ha che
:<math>x\equiv y\mod a,~~~~x\equiv z\mod b</math>
Quindi, poiché ridurre modulo ''n'' non cambia l'essere coprimo con ''n'', ''x'' è coprimo con ''ab'' se e solo se ''y'' è coprimo con ''a'' e ''z'' con ''b''. Per quanto abbiamo dimostrato precedentemente, ogni coppia (''y'',''z'') di elementi coprimi (rispettivamente con ''a'' e ''b'') corrisponde ad un unico ''x'' coprimo con ''ab'' e, viceversa, ogni ''x'' coprimo con ''ab'' corrispondente ad una coppia (''y'',''z''). Ora questo tipo di coppie sono <math>\phi\left(a\right)\phi(b)</math> (essendo <math>\phi\left(n\right)</math> la quantità di numeri minori di ''n'' coprimi con ''n''), mentre il numero di ''x'' coprimi con ''ab'' è <math>\phi\left(ab\right)</math>; poiché questi due numeri sono uguali,
:<math>\phi\left(ab\right)=\phi(a)\phi(b)</math>
== Il lemma di Thue ==
| |||