Aritmetica modulare/Congruenze lineari: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
applicazione alla funzione di eulero |
→Un'applicazione: la funzione di Eulero: precisazione |
||
Riga 102:
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> (dove ''a'' e ''b'' sono tra loro coprimi), 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>
per ogni coppia di ''a'' e ''b'' coprimi.
== Il lemma di Thue ==
| |||