Teorema di Fermat generale.
Moderatore: tutor
- psion_metacreativo
- Messaggi: 645
- Iscritto il: 01 gen 1970, 01:00
C\'è qualcuno che ha risolto l\'esercizio a pag 89 del courant, chiede di dimostrare che se a è primo con n allora:
<BR>
<BR> a^φ(n) ≡ 1 (mod n)
<BR>
<BR>φ(n) è la funzione di Eulero che associa ad n il numero dei numeri minori di n tali che il loro massimo comun divisore con n è 1, è definita così
<BR>
<BR>n= p1^a1p2^a2....pn^an (scomposizione in fattori primi di n)
<BR>
<BR>φ(n) = n(1-1/p1)(1-1/p2)...(1-1/pn)
<BR>
<BR>Potete scrivermi la dimostrazione che non ho idea di dove partire. Grazie.
<BR>
<BR> a^φ(n) ≡ 1 (mod n)
<BR>
<BR>φ(n) è la funzione di Eulero che associa ad n il numero dei numeri minori di n tali che il loro massimo comun divisore con n è 1, è definita così
<BR>
<BR>n= p1^a1p2^a2....pn^an (scomposizione in fattori primi di n)
<BR>
<BR>φ(n) = n(1-1/p1)(1-1/p2)...(1-1/pn)
<BR>
<BR>Potete scrivermi la dimostrazione che non ho idea di dove partire. Grazie.
La dimostrazione, per chi la volesse, si può trovare nel libro \"Il numero\", di Midhat Gazalè, pagg. 144-145.
<BR>
<BR>Supponiamo che i residui relativamente primi di d siano p1, p2,... p[φ(n)]; d\'ora in avanti, per comodità, li chiamerò semplicemente residui. Calcoliamo i residui (mod n) di a moltiplicato per ciascun residuo primo di n, e chiamiamoli subresidui.
<BR>otteniamo che:
<BR>1. Essendo a e tutti i p primi con n, anche i subresidui lo saranno. Pertanto i subresidui apparterranno tutti all\'insieme (parentesi graffa) p1, p2,... p[φ(n)] (chiusa parentesi graffa).
<BR>2.Se per assurdo ci fossero due residui distinti px, py tali che a*px==a*py (mod n), essendo a primo con n si può dividere tutto per a, ottenendo px==py (mod n). Ma essendo che tutti i residui sono minori di n, si dovrebbe avere px=py, in contraddizione con l\'assunto che px e py sono distinti. Pertanto tutti i subresidui sono diversi tra loro, ed essendo che il numero di residui è uguale al numero di subresidui, allora i due insiemi sono uguali.
<BR>Adesso calcoliamo il residuo (mod n) del prodotto dei subresidui
<BR>P= (a*p1)*(a*p2)*...(a*p[φ(n)])== p1*p2*...p[φ(n)] (mod n)
<BR>Ma d\'altra parte
<BR>P= (a*p1)*(a*p2)*...(a*p[φ(n)])= a^φ(n)*(p1*p2*...p[φ(n)]).
<BR>Perciò a^φ(n)*(p1*p2*...p[φ(n)])== p1*p2*...p[φ(n)] (mod n), e poichè il prodotto dei residui è primo con n, possiamo toglierlo comodamente dai due membri dell\'uguaglianza, ottenendo
<BR>a^φ(n) ≡ 1 (mod n).
<BR>
<BR>
<BR>...più o meno...
<BR>
<BR>Supponiamo che i residui relativamente primi di d siano p1, p2,... p[φ(n)]; d\'ora in avanti, per comodità, li chiamerò semplicemente residui. Calcoliamo i residui (mod n) di a moltiplicato per ciascun residuo primo di n, e chiamiamoli subresidui.
<BR>otteniamo che:
<BR>1. Essendo a e tutti i p primi con n, anche i subresidui lo saranno. Pertanto i subresidui apparterranno tutti all\'insieme (parentesi graffa) p1, p2,... p[φ(n)] (chiusa parentesi graffa).
<BR>2.Se per assurdo ci fossero due residui distinti px, py tali che a*px==a*py (mod n), essendo a primo con n si può dividere tutto per a, ottenendo px==py (mod n). Ma essendo che tutti i residui sono minori di n, si dovrebbe avere px=py, in contraddizione con l\'assunto che px e py sono distinti. Pertanto tutti i subresidui sono diversi tra loro, ed essendo che il numero di residui è uguale al numero di subresidui, allora i due insiemi sono uguali.
<BR>Adesso calcoliamo il residuo (mod n) del prodotto dei subresidui
<BR>P= (a*p1)*(a*p2)*...(a*p[φ(n)])== p1*p2*...p[φ(n)] (mod n)
<BR>Ma d\'altra parte
<BR>P= (a*p1)*(a*p2)*...(a*p[φ(n)])= a^φ(n)*(p1*p2*...p[φ(n)]).
<BR>Perciò a^φ(n)*(p1*p2*...p[φ(n)])== p1*p2*...p[φ(n)] (mod n), e poichè il prodotto dei residui è primo con n, possiamo toglierlo comodamente dai due membri dell\'uguaglianza, ottenendo
<BR>a^φ(n) ≡ 1 (mod n).
<BR>
<BR>
<BR>...più o meno...
-
- Messaggi: 774
- Iscritto il: 01 gen 1970, 01:00
Sia Z/nZ (zeta modulo enne zeta) l\'insieme delle classi resto modulo n. Si indica con (Z/nZ)* l\'insieme delle classi che hanno un inverso in Z/nZ. Ad esempio (Z/10Z)*={1,3,7,9} poiché 1*1=1, 3*7=1, 9*9=1 e gli altri non sono invertibili. G=(Z/nZ)* consta di tutte e sole le classi i cui rappresentanti sono primi con n ed è un gruppo moltiplicativo di ordine phi(n). Poiché in ogni gruppo finito un elemento elevato alla ordine del gruppo fa l\'identità, nel nostro caso si ha a^phi(n)=1 in G per ogni a in G, da cui segue subito la tesi.
<BR>Se non tutto è chiaro domandate.
<BR>
<BR>ps: queste cose dovete chiederle a EvaristeG, è lui che ha sviluppato la teoria dei gruppi. Peccato sia morto a 21 anni...<BR><BR>[ Questo Messaggio è stato Modificato da: Lucio il 09-06-2003 13:14 ]
<BR>Se non tutto è chiaro domandate.
<BR>
<BR>ps: queste cose dovete chiederle a EvaristeG, è lui che ha sviluppato la teoria dei gruppi. Peccato sia morto a 21 anni...<BR><BR>[ Questo Messaggio è stato Modificato da: Lucio il 09-06-2003 13:14 ]
- psion_metacreativo
- Messaggi: 645
- Iscritto il: 01 gen 1970, 01:00
Riprendo solo ora questo topic perchè prima non ci potevo capire nulla, invece oggi tornando a vedere i bei tempi passati ho ritrovato questo intervento di Lucio che stranamente mi è apparso molto più chiaro, direi limpido, sebbene rimangono ancora alcuni dubbi, in particolare 2:
<BR>
<BR>1)
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>G=(Z/nZ)* consta di tutte e sole le classi i cui rappresentanti sono primi con n ed <!-- BBCode Start --><B>è un gruppo moltiplicativo</B><!-- BBCode End --> di ordine phi(n).
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>come lo dimostri la proposizione in neretto?
<BR>
<BR>2)
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>Poiché in ogni gruppo finito un elemento elevato alla ordine del gruppo fa l\'identità
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>cosa vuol dire esattamente? Si può avere qualche accenno su questi gruppi moltiplicativi?
<BR>
<BR>1)
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>G=(Z/nZ)* consta di tutte e sole le classi i cui rappresentanti sono primi con n ed <!-- BBCode Start --><B>è un gruppo moltiplicativo</B><!-- BBCode End --> di ordine phi(n).
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>come lo dimostri la proposizione in neretto?
<BR>
<BR>2)
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>Poiché in ogni gruppo finito un elemento elevato alla ordine del gruppo fa l\'identità
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>cosa vuol dire esattamente? Si può avere qualche accenno su questi gruppi moltiplicativi?
io ti dico quello che so, ma non ti assicuro che sia giusto
<BR>
<BR>un gruppo finito G è un insieme finito dotato di un\'operazione binaria *, tale che
<BR>-per ogni a,b in G => a*b è in G
<BR>-esiste e in G tale che per ogni a in G a*e=a
<BR>-per goni a in G, esiste a<sup>-1</sup> in G, tale che a*a<sup>-1</sup>=a<sup>-1</sup>*a=e
<BR>-per ogni a,b,c in G, (a*b)*c=a*(b*c)
<BR>
<BR>non so a cosa si riferisca Lucio con l\'aggettivo \"moltiplicativo\"
<BR>
<BR>l\'ordine di un gruppo (finito) è il numero dei suoi elementi
<BR>
<BR>se d è l\'ordine di G, per ongi a in G
<BR>a<sup>d</sup>(=a*a*...*a d volte)=e
<BR>
<BR>chiaro?
<BR>
<BR>per gli univarsitari che hanno studiato la teoria dei gruppi: se ho detto delle boiate correggetemi!! <IMG SRC="images/forum/icons/icon_smile.gif"> <BR><BR>[ Questo Messaggio è stato Modificato da: talpuz il 28-02-2004 20:26 ]
<BR>
<BR>un gruppo finito G è un insieme finito dotato di un\'operazione binaria *, tale che
<BR>-per ogni a,b in G => a*b è in G
<BR>-esiste e in G tale che per ogni a in G a*e=a
<BR>-per goni a in G, esiste a<sup>-1</sup> in G, tale che a*a<sup>-1</sup>=a<sup>-1</sup>*a=e
<BR>-per ogni a,b,c in G, (a*b)*c=a*(b*c)
<BR>
<BR>non so a cosa si riferisca Lucio con l\'aggettivo \"moltiplicativo\"
<BR>
<BR>l\'ordine di un gruppo (finito) è il numero dei suoi elementi
<BR>
<BR>se d è l\'ordine di G, per ongi a in G
<BR>a<sup>d</sup>(=a*a*...*a d volte)=e
<BR>
<BR>chiaro?
<BR>
<BR>per gli univarsitari che hanno studiato la teoria dei gruppi: se ho detto delle boiate correggetemi!! <IMG SRC="images/forum/icons/icon_smile.gif"> <BR><BR>[ Questo Messaggio è stato Modificato da: talpuz il 28-02-2004 20:26 ]
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]
Una banalita\'.
<BR>Un gruppo e\' detto <!-- BBCode Start --><B>moltiplicativo</B><!-- BBCode End --> se l\'operazione
<BR>binaria in esso definita e\' indicata con il segno \"*\".
<BR>Ovviamente si tratta di una distinzione puramente
<BR>formale a meno che l\'operazione binaria in questione
<BR>non coincida proprio con l\'ordinaria moltiplicazione.
<BR>
<BR>Un gruppo e\' detto <!-- BBCode Start --><B>moltiplicativo</B><!-- BBCode End --> se l\'operazione
<BR>binaria in esso definita e\' indicata con il segno \"*\".
<BR>Ovviamente si tratta di una distinzione puramente
<BR>formale a meno che l\'operazione binaria in questione
<BR>non coincida proprio con l\'ordinaria moltiplicazione.
<BR>
- massiminozippy
- Messaggi: 736
- Iscritto il: 01 gen 1970, 01:00
<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-02-28 20:26, talpuz wrote:
<BR>
<BR>un gruppo finito G è un insieme finito dotato di un\'operazione binaria *, tale che
<BR>-per ogni a,b in G => a*b è in G
<BR>-esiste e in G tale che per ogni a in G a*e=a
<BR>-per goni a in G, esiste a<sup>-1</sup> in G, tale che a*a<sup>-1</sup>=a<sup>-1</sup>*a=e
<BR>-per ogni a,b,c in G, (a*b)*c=a*(b*c)
<BR>
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>\"Oppure\" puoi definire l\'operazione * in modo che sia binaria e interna di modo che per definire un gruppo bastano le ultime tre proprietà.
<BR>
<BR>On 2004-02-28 20:26, talpuz wrote:
<BR>
<BR>un gruppo finito G è un insieme finito dotato di un\'operazione binaria *, tale che
<BR>-per ogni a,b in G => a*b è in G
<BR>-esiste e in G tale che per ogni a in G a*e=a
<BR>-per goni a in G, esiste a<sup>-1</sup> in G, tale che a*a<sup>-1</sup>=a<sup>-1</sup>*a=e
<BR>-per ogni a,b,c in G, (a*b)*c=a*(b*c)
<BR>
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>\"Oppure\" puoi definire l\'operazione * in modo che sia binaria e interna di modo che per definire un gruppo bastano le ultime tre proprietà.
<BR>
- psion_metacreativo
- Messaggi: 645
- Iscritto il: 01 gen 1970, 01:00
Ok ora che so cos\'è un gruppo moltiplicativo come si dimostra che
<BR>
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>
<BR>G=(Z/nZ)* consta di tutte e sole le classi i cui rappresentanti sono primi con n ed <!-- BBCode Start --><B>è un gruppo moltiplicativo</B><!-- BBCode End --> di ordine phi(n).
<BR>
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>?
<BR>
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>
<BR>G=(Z/nZ)* consta di tutte e sole le classi i cui rappresentanti sono primi con n ed <!-- BBCode Start --><B>è un gruppo moltiplicativo</B><!-- BBCode End --> di ordine phi(n).
<BR>
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>?
allora...
<BR>- per ogni (a,b) in G, a*b € G, visto che MCD(a,n) = 1, MCD(b,n) = 1 => MCD(ab,n) = 1.
<BR>- MCD(1,n) = 1, e a*1 = a per ogni a, in particolare per ogni a € G. e = 1.
<BR>- per ogni a € G, esiste a<sup>-1</sup> € G tale che aa<sup>-1</sup> = 1, essendo ogni elemento primo con n invertibile mod n (è sempre possibile risolvere una diofantea con i coefficienti primi tra loro, come sarebbe in questo caso: fissati a ed n primi tra loro, è sufficiente trovare a<sup>-1</sup> e k tali che aa<sup>-1</sup> + kn = 1).
<BR>- l\'operazione è associativa, e non è difficile da dimostrare... posso lasciarti quest\'onere??
<BR>- inoltre è anche commutativa, ovviamente...
<BR>si parla di gruppo commutativo, se non erro...
<BR>- per ogni (a,b) in G, a*b € G, visto che MCD(a,n) = 1, MCD(b,n) = 1 => MCD(ab,n) = 1.
<BR>- MCD(1,n) = 1, e a*1 = a per ogni a, in particolare per ogni a € G. e = 1.
<BR>- per ogni a € G, esiste a<sup>-1</sup> € G tale che aa<sup>-1</sup> = 1, essendo ogni elemento primo con n invertibile mod n (è sempre possibile risolvere una diofantea con i coefficienti primi tra loro, come sarebbe in questo caso: fissati a ed n primi tra loro, è sufficiente trovare a<sup>-1</sup> e k tali che aa<sup>-1</sup> + kn = 1).
<BR>- l\'operazione è associativa, e non è difficile da dimostrare... posso lasciarti quest\'onere??
<BR>- inoltre è anche commutativa, ovviamente...
<BR>si parla di gruppo commutativo, se non erro...