Qualcuno può postare la dimostrazione del teorema di Eulero-Fermat o indicarmi un link che la contenga?
<BR>
<BR>Il teorema di Eulero-Fermat afferma che, se si hanno due interi tali che
<BR>
<BR>gcd (a,b)=1 allora a^(phi(b)) è congruo a 1 mod b
<BR>
<BR>Grazie<BR><BR>[ Questo Messaggio è stato Modificato da: XT il 28-10-2003 15:01 ]
Euler-Fermat
Moderatore: tutor
-
psion_metacreativo
- Messaggi: 645
- Iscritto il: 01 gen 1970, 01:00
Definiamo A={a_i : (a_i,m)=1} e definiamo Ax={xa_i : a_i è in A} con x fissato e preso in A. |A|=phi(m)
<BR>si dimostra facilmente (fattelo!!) che tutti gli elementi di A e tutti gli elementi di Ax sono tra loro distinti; quindi per ogni elem di Ax esiste un elem di A che gli è congruo mod m. A questo punto il prodotto di tutti gli elementi di A (P_A) è uguale al prodotto di tutti gli elementi di Ax e cioè si ha:
<BR>x^(phi(m))*P_A==P_A (mod m)
<BR>semplificando
<BR>x^(phi(m))=1 (mod m).
<BR>
<BR>cvd
<BR>
<BR>PS: in alternativa puoi dire che se un gruppo G ha n elementi, per ogni x in G, si ha che x^n=1 dove 1 è l\'elem neutro di G. Da cui il teorema. <IMG SRC="images/forum/icons/icon21.gif">
<BR>si dimostra facilmente (fattelo!!) che tutti gli elementi di A e tutti gli elementi di Ax sono tra loro distinti; quindi per ogni elem di Ax esiste un elem di A che gli è congruo mod m. A questo punto il prodotto di tutti gli elementi di A (P_A) è uguale al prodotto di tutti gli elementi di Ax e cioè si ha:
<BR>x^(phi(m))*P_A==P_A (mod m)
<BR>semplificando
<BR>x^(phi(m))=1 (mod m).
<BR>
<BR>cvd
<BR>
<BR>PS: in alternativa puoi dire che se un gruppo G ha n elementi, per ogni x in G, si ha che x^n=1 dove 1 è l\'elem neutro di G. Da cui il teorema. <IMG SRC="images/forum/icons/icon21.gif">