Tu fatti i fattoriali tuoi...

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Bloccato
euler_25
Messaggi: 428
Iscritto il: 01 gen 1970, 01:00
Località: mooolto vicino...

Messaggio da euler_25 » 01 gen 1970, 01:33

<!-- BBCode Start --><B>Problema i)</B><!-- BBCode End --> (teorema di Wilson): provare che, per ogni numero primo p, risulta: (p-1)! ≡ -1 (mod p). Dell\'asserto sarebbe gradita una dimostrazione <!-- BBCode Start --><I>elementare</I><!-- BBCode End -->, che non faccia impiego della moderna Teoria dei Gruppi applicata allo studio degli interi.
<BR>
<BR><!-- BBCode Start --><B>Problema ii)</B><!-- BBCode End -->: dimostrare che, comunque fissato un intero n > 2, esiste almeno un numero primo p tale che n < p < n!.
<BR>
<BR><!-- BBCode Start --><B>Problema iii)</B><!-- BBCode End -->: dopo aver dimostrato che 10! - 1 è divisibile per 29, <!-- BBCode Start --><I>dedurne</I><!-- BBCode End --> che 18! + 1 gode anch\'esso della medesima proprietà.
<BR>
<BR>Questi problemi sono un omaggio ad un caro personaggio del forum, con il quale ho scoperto di condividere un certo interesse per i fattoriali... ghghgh!!!
<center>Le cose cambiano... e i sentimenti pure...</center>

EvaristeG
Site Admin
Messaggi: 4791
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG » 01 gen 1970, 01:33

i) Visto che è uno dei pochi problemi di teoria dei numeri a cui io abbia mai risposto, mi autocito
<BR>http://olimpiadi.ing.unipi.it/modules.p ... 05&forum=5
<BR>E poichè non ero ancora all\'università certo non sapevo nulla di t dei gruppi (non che adesso ne sappia poi molto... <IMG SRC="images/forum/icons/icon_confused.gif"> )
<BR> <IMG SRC="images/forum/icons/icon_wink.gif">
<BR>
<BR>Chi voglia farselo da solo, basta che non apra il link.

euler_25
Messaggi: 428
Iscritto il: 01 gen 1970, 01:00
Località: mooolto vicino...

Messaggio da euler_25 » 01 gen 1970, 01:33

Ouch!!! E vabbé, che ne potevo sapere? Comunque mo\' vado a leggermela! Chissà che... ghghgh... ghghgh... <IMG SRC="images/forum/icons/icon_smile.gif">
<BR>
<BR>P.S.: in ogni caso, come suggerisce lo stesso Evariste, provate a risolverlo a modo vostro, prima di andarvi a scorrere la sua dimostrazione! Su su! <IMG SRC="images/forum/icons/icon_biggrin.gif">
<center>Le cose cambiano... e i sentimenti pure...</center>

euler_25
Messaggi: 428
Iscritto il: 01 gen 1970, 01:00
Località: mooolto vicino...

Messaggio da euler_25 » 01 gen 1970, 01:33

Uhm... Evariste, il tuo ragionamento è mooolto carino, però c\'è qualcosa che non mi quadra... uhm... senti un po\' qua! Te affermi 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>...tra gli altri numeri da 1 a p-1, <!-- BBCode Start --><B>potremo formare delle coppie tali che il loro prodotto dia a</B><!-- BBCode End -->. Quindi avremo tra i numeri da 1 a p-1, una coppia di numeri x e p-x tali che x(p-x) ≡ -a mod p e <!-- BBCode Start --><B>1/2(p-3) coppie di numeri diversi il cui prodotto è ≡ a mod p</B><!-- BBCode End -->. Allora (p-1)! ≡ -a*a^(1/2(p-3)) ≡ -a^(1/2(p-1))...
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Ora, mi chiarisci un punto? Le (p-3)/2 coppie <!-- BBCode Start --><I>distinte</I><!-- BBCode End --> di cui te riferisci nel tuo post non sono tutte della forma (x<sub>i</sub>, p-x<sub>i</sub>), con x<sub>i</sub> != x, per i = 1, 2, ..., (p-3)/2? <IMG SRC="images/forum/icons/icon_confused.gif">
<center>Le cose cambiano... e i sentimenti pure...</center>

Biagio
Messaggi: 535
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Biagio » 01 gen 1970, 01:33

anch\'io mi autocito:
<BR>1)
<BR>ecco come ho fatto io:
<BR>se p è primo allora esiste un generatore g tale che per i che va da 1 a p-1, g^i assume tutti i valori di congruenza mod(p) tra 1 e p-1 allora (p-1)!==g^1g^2g^3....g^(p-1)==g^(p(p-1)/2) mod(p) da cui si ricava che p(p-1)/2==(p-1)/2 mod(p-1) allora g^(p(p-1)/2)==g^((p-1)/2)==-1 mod p
<BR>
<BR>
<BR>
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: Biagio il 11-02-2004 23:25 ]

euler_25
Messaggi: 428
Iscritto il: 01 gen 1970, 01:00
Località: mooolto vicino...

Messaggio da euler_25 » 01 gen 1970, 01:33

<!-- 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-11 23:23, Biagio wrote:
<BR>se p è primo allora esiste un generatore g tale che per i che va da 1 a p-1, g^i assume tutti i valori di congruenza mod(p) tra 1 e p-1 allora (p-1)! ≡ g^1g^2g^3....g^(p-1) ≡ g^(p(p-1)/2) mod(p) da cui si ricava che p(p-1)/2 ≡(p-1)/2 mod(p-1) allora g^(p(p-1)/2) ≡ <!-- BBCode Start --><B>g^((p-1)/2) ≡ -1 mod p</B><!-- BBCode End -->
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Uhm... Biagio, la tua dimostrazione <!-- BBCode Start --><I>potrebbe essere corretta</I><!-- BBCode End -->, ma non posso accordarle incondizionatamente il mio <!-- BBCode Start --><I>placet</I><!-- BBCode End -->! Beh, innanzitutto, l\'affermazione secondo cui la congruenza: p(p-1)/2 ≡(p-1)/2 (mod p-1) sarebbe conseguenza dell\'altra: (p-1)! ≡ g^(p(p-1)/2) (mod p) mi lascia... come dire... un tantino interdetto... ma questo (dopo tutto) è soltanto un dettaglio...! Ché d\'altro canto, Biagio, mi spiegheresti cosa ci azzecca la tua dimostrazione con il problema da me proposto? Sbaglierò ma mi era parso d\'aver vietato esplicitamente il ricorso alla Teoria dei Gruppi!!! Ci ho torto forse? Beh, mi par proprio non vi sia d\'aspettar che tu risponda... e allora, come la mettiamo? Cos\'è questa storia dei generatori? Bah, in effetti può anche darsi che tu conosca la teoria classica di Gauss sulle radici primitive dell\'unità e che a questo te ti voglia riferire col tuo discorso sui generatori... il che tuttavia (se posso essere sincero...) mi sembra in effetti poco verosimile!?! In ogni caso, poiché non è da escludersi quest\'evenienza, ti concedo (se non altro) il privilegio del dubbio, in attesa di poter conoscere le tue ragioni... ciao, Biagio! <IMG SRC="images/forum/icons/icon21.gif">
<BR>
<BR>P.S.: e poi un\'altra domanda, tanto per rompere i maroni... mi chiarisci quale condizione t\'assicura la consistenza della congruenza: <!-- BBCode Start --><B>g^((p-1)/2) ≡ -1 mod p</B><!-- BBCode End -->. In altre parole... cosa ti garantisce che g non sia un residuo quadratico modulo p? Uhm... grazie, Biagio... <IMG SRC="images/forum/icons/icon_wink.gif">
<BR>
<BR>EDIT: mi son levato dal letto con il pensiero! Biagio, sia ben chiaro, ché non vorrei essere frainteso. Lo <!-- BBCode Start --><I>statement</I><!-- BBCode End --> che ho evidenziato è <!-- BBCode Start --><B>assolutamente corretto</B><!-- BBCode End -->. Soltanto, poiché non reputo che sia un fatto banale..., ritengo sarebbe il caso di spenderci su qualche parolina in più! <IMG SRC="images/forum/icons/icon_smile.gif"><BR><BR>[ Questo Messaggio è stato Modificato da: euler_25 il 12-02-2004 09:05 ]
<center>Le cose cambiano... e i sentimenti pure...</center>

ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Messaggio da ma_go » 01 gen 1970, 01:33

ii) se ti dico \"teorema di chebycheff\"? mi sputi in faccia, immagino! *
<BR>comunque esiste (e non è difficile) una dimostrazione elementare...
<BR>
<BR>
<BR>* il teorema di chebycheff afferma che tra n e 2n+2 esistono sempre due primi distinti, se non vado errando

euler_25
Messaggi: 428
Iscritto il: 01 gen 1970, 01:00
Località: mooolto vicino...

Messaggio da euler_25 » 01 gen 1970, 01:33

<!-- 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-12 13:40, ma_go wrote:
<BR>ii) se ti dico \"teorema di chebycheff\"? mi sputi in faccia, immagino! *
<BR>comunque esiste (e non è difficile) una dimostrazione elementare...
<BR>
<BR>* il teorema di chebycheff afferma che tra n e 2n+2 esistono sempre due primi distinti, se non vado errando
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>OK, ma_go! La tua soluzione mi va più che bene! Del resto, il teorema di Chebichev (al secolo, postulato di Bertrand, fra gli altri dimostrato per via elementare dal compianto Erdos) è un risultato troppo importante per non applicarlo là dove l\'occorrenza vi si presti! Quindi... OK!!!
<BR>
<BR>P.S.: tanto per la cronaca, mi risulta cmq che la formulazione <!-- BBCode Start --><I>originale</I><!-- BBCode End --> del risultato di cui te, ma_go, hai fatto impiego è data piuttosto nei termini seguenti (t\'inviterei a controllare meglio le tue fonti e farmi quindi sapere):
<BR>
<BR><!-- BBCode Start --><B>Teorema di Chebichev:</B><!-- BBCode End --> comunque fissato un n intero > 1, esiste sempre <!-- BBCode Start --><I>almeno</I><!-- BBCode End --> un numero primo p tale che: n < p < 2n.<BR><BR>[ Questo Messaggio è stato Modificato da: euler_25 il 12-02-2004 14:37 ]
<center>Le cose cambiano... e i sentimenti pure...</center>

Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz » 01 gen 1970, 01:33

ok, ora tocca a me autocitarmi.. <IMG SRC="images/forum/icons/icon_biggrin.gif">
<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>ogni numero a compreso tra 1 e p-1 ha un inverso nello stesso intervallo (cioè un numero b tale ab==1 mod p)
<BR>eccettuati quindi quei numeri per cui a^2==1 ==> a==+1 o a==-1 che sono 1 e p-1, tutti gli altri si possono accoppiare in modo che il prodotto di ogni coppia sia ==1 mod p
<BR>quindi 1*2*3*...*(p-2)==1 mod p
<BR>moltiplicando per p-1 (che è ==-1 mod p) si ha la tesi
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]

EvaristeG
Site Admin
Messaggi: 4791
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG » 01 gen 1970, 01:33

Non ho capito cosa tu voglia chiedere...cmq quello che intendevo è:
<BR>Esistono due numeri - chiamiamoli x e (p-x) - che sono le radici quadrate di a, mentre per ogni altro numero y tra 1 e p-1 esiste a*y^(-1) e quindi possiamo formare (p-1-2)/2 coppie di elementi (compresi tra 1 e p-1) che a due a due diano come prodotto a.
<BR>Rimangono x e (p-x) che tra loro moltiplicati danno -a.
<BR>Da cui i contazzi che seguono; in realtà non mi interessa minimamente che forma abbiano le coppie di fattori....
<BR>

Biagio
Messaggi: 535
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Biagio » 01 gen 1970, 01:33

<!-- 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-12 02:26, euler_25 wrote:
<BR>Beh, innanzitutto, l\'affermazione secondo cui la congruenza: p(p-1)/2 ≡(p-1)/2 (mod p-1) sarebbe conseguenza dell\'altra: (p-1)! ≡ g^(p(p-1)/2) (mod p) mi lascia... come dire... un tantino interdetto... ma questo (dopo tutto) è soltanto un dettaglio...!
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>infatti, è un dettaglio
<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>On 2004-02-12 02:26, euler_25 wrote:
<BR>Ché d\'altro canto, Biagio, mi spiegheresti cosa ci azzecca la tua dimostrazione con il problema da me proposto? Sbaglierò ma mi era parso d\'aver vietato esplicitamente il ricorso alla Teoria dei Gruppi!!! Ci ho torto forse? Beh, mi par proprio non vi sia d\'aspettar che tu risponda... e allora, come la mettiamo? Cos\'è questa storia dei generatori? Bah, in effetti può anche darsi che tu conosca la teoria classica di Gauss sulle radici primitive dell\'unità e che a questo te ti voglia riferire col tuo discorso sui generatori... il che tuttavia (se posso essere sincero...) mi sembra in effetti poco verosimile!?! In ogni caso, poiché non è da escludersi quest\'evenienza, ti concedo (se non altro) il privilegio del dubbio, in attesa di poter conoscere le tue ragioni... ciao, Biagio! <IMG SRC="images/forum/icons/icon21.gif">
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>non so che cosa sia la teoria dei gruppi, infatti!è solo che per sapere che cos\'è un generatore basta molto meno...per esempio leggere la dispensa di Gobbino, Bibbia degli olimpionici.
<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>On 2004-02-12 02:26, euler_25 wrote:
<BR>P.S.: e poi un\'altra domanda, tanto per rompere i maroni... mi chiarisci quale condizione t\'assicura la consistenza della congruenza: <!-- BBCode Start --><B>g^((p-1)/2) ≡ -1 mod p</B><!-- BBCode End -->. In altre parole... cosa ti garantisce che g non sia un residuo quadratico modulo p? Uhm... grazie, Biagio... <IMG SRC="images/forum/icons/icon_wink.gif">
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>questa è una proprietà dei generatori
<BR>

euler_25
Messaggi: 428
Iscritto il: 01 gen 1970, 01:00
Località: mooolto vicino...

Messaggio da euler_25 » 01 gen 1970, 01:33

Bene, Biagio!!! Prendo atto delle tue... hmm hmm... ragioni!?! Ma siccome vorrei approfondire questo aspetto della faccenda..., propongo allora un altro bell\'esercizietto, che tira in ballo (senza mezzi termini) la proprietà che te hai utilizzato nella dimostrazione del teorema di Wilson... ghghgh...
<BR>
<BR><!-- BBCode Start --><B>Problema iv)</B><!-- BBCode End -->: dimostrare che, comunque considerato un numero primo p > 2, esiste almeno un intero positivo 1 < g < p tale che: g<sup>k</sup> !≡ 1 (mod p), per ogni k = 1, 2, ..., p-2.
<BR>
<BR><!-- BBCode Start --><B>NOTA</B><!-- BBCode End -->: <!-- BBCode Start --><I>è vietato ogni ricorso alla Teoria dei Gruppi... grazie!!!</I><!-- BBCode End --><BR><BR>[ Questo Messaggio è stato Modificato da: euler_25 il 12-02-2004 22:34 ]
<center>Le cose cambiano... e i sentimenti pure...</center>

euler_25
Messaggi: 428
Iscritto il: 01 gen 1970, 01:00
Località: mooolto vicino...

Messaggio da euler_25 » 01 gen 1970, 01:33

<!-- 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-12 19:29, EvaristeG wrote:
<BR>Non ho capito cosa tu voglia chiedere...cmq quello che intendevo è:
<BR>Esistono due numeri - chiamiamoli x e (p-x) - che sono le radici quadrate di a, mentre per ogni altro numero y tra 1 e p-1 esiste a*y^(-1) e quindi possiamo formare (p-1-2)/2 coppie di elementi (compresi tra 1 e p-1) che a due a due diano come prodotto a.
<BR>Rimangono x e (p-x) che tra loro moltiplicati danno -a.
<BR>Da cui i contazzi che seguono; in realtà non mi interessa minimamente che forma abbiano le coppie di fattori...
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Bene, avevo frainteso io, Evariste! Meglio così, adesso mi è tutto chiaro! <IMG SRC="images/forum/icons/icon_razz.gif">
<center>Le cose cambiano... e i sentimenti pure...</center>

euler_25
Messaggi: 428
Iscritto il: 01 gen 1970, 01:00
Località: mooolto vicino...

Messaggio da euler_25 » 01 gen 1970, 01:33

<!-- 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-12 19:23, talpuz wrote:
<BR>ogni numero a compreso tra 1 e p-1 ha un inverso nello stesso intervallo (cioè un numero b tale ab==1 mod p)
<BR>eccettuati quindi quei numeri per cui a^2==1 ==> a==+1 o a==-1 che sono 1 e p-1, tutti gli altri si possono accoppiare in modo che il prodotto di ogni coppia sia ==1 mod p
<BR>quindi 1*2*3*...*(p-2)==1 mod p
<BR>moltiplicando per p-1 (che è ==-1 mod p) si ha la tesi
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Bene, in effetti anch\'io (a suo tempo) avevo adottato questo medesimo approccio, per cui (a costo di sembrare un po\' di parte...) ti dico che la TUA, Talpuz, è la dimostrazione che in assoluto preferisco... ghghgh... <IMG SRC="images/forum/icons/icon_wink.gif">
<BR>
<BR>Ché del resto... <!-- BBCode Start --><I>de gustibus non disputandum est</I><!-- BBCode End -->! <IMG SRC="images/forum/icons/icon21.gif">
<center>Le cose cambiano... e i sentimenti pure...</center>

Bloccato