Teorema di Fermat generale.

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Bloccato
Avatar utente
psion_metacreativo
Messaggi: 645
Iscritto il: 01 gen 1970, 01:00

Messaggio da psion_metacreativo »

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.
Avatar utente
info
Messaggi: 903
Iscritto il: 01 gen 1970, 01:00

Messaggio da info »

Psion......anch\'io mi ero posto quel problema e mi ero dato una sol lunga ed assurda. Avevo utilizzato una dim intermedia che avevo proposto nel forum tempo fa ( vai a: proponi gli es, seconda pagina). Guardale e fatti 2 risate.............
ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Messaggio da ma_go »

io partirei dal piccolo teorema di fermat per a primo, poi farei un bel sistema di congruenze che si dimostra dare come soluzione a == 1 (mod n), non dev\'essere difficile...
<BR>e, se non funzionasse, è perché è la prima cosa che mi è venuta in mente ora in laboratorio...
Avatar utente
info
Messaggi: 903
Iscritto il: 01 gen 1970, 01:00

Messaggio da info »

Nn capisco.....a nn deve essere primo, ma primo con n......e poi anche se a fosse primo, fermat nn dice che se a^(p-1)=1 (mod p) allora a=1 (mod p). Controesempio: 5^12=1 (mod 13) ma 5=5 (mod 13). Inoltre, tornando a fermat generalizzato, 5^4=1 (mod 12) ma 5=5 (mod 12) Parlo a vanvera?
<BR> InFo
Mathema
Messaggi: 124
Iscritto il: 01 gen 1970, 01:00
Località: Torino

Messaggio da Mathema »

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...
publiosulpicio
Messaggi: 774
Iscritto il: 01 gen 1970, 01:00

Messaggio da publiosulpicio »

La chiave della dimostrazione sta nel fatto che se si considerano i multipli di a per i primi con n si ottiene ancora un \"complete set\" (non so tradurlo\" di resti, insomma ancora numero congri ai primi con n. mi accorgo che non si capice nulla...
Lucio
Messaggi: 180
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da Lucio »

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 ]
Avatar utente
psion_metacreativo
Messaggi: 645
Iscritto il: 01 gen 1970, 01:00

Messaggio da psion_metacreativo »

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?
Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz »

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 ]
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]
Avatar utente
karl
Messaggi: 926
Iscritto il: 01 gen 1970, 01:00

Messaggio da karl »

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>
Avatar utente
massiminozippy
Messaggi: 736
Iscritto il: 01 gen 1970, 01:00

Messaggio da massiminozippy »

<!-- 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>
Avatar utente
psion_metacreativo
Messaggi: 645
Iscritto il: 01 gen 1970, 01:00

Messaggio da psion_metacreativo »

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>?
ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Messaggio da ma_go »

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...
Bloccato