Tu fatti i fattoriali tuoi...

euler_25 · Messaggio da **euler_25** » 01 gen 1970, 01:33

Problema i) (teorema di Wilson): provare che, per ogni numero primo p, risulta: (p-1)! ≡ -1 (mod p). Dell\'asserto sarebbe gradita una dimostrazione elementare, che non faccia impiego della moderna Teoria dei Gruppi applicata allo studio degli interi.
 
 Problema ii): dimostrare che, comunque fissato un intero n > 2, esiste almeno un numero primo p tale che n 
 Problema iii): dopo aver dimostrato che 10! - 1 è divisibile per 29, dedurne che 18! + 1 gode anch\'esso della medesima proprietà.
 
 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!!!

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
 http://olimpiadi.ing.unipi.it/modules.p ... 05&forum=5
 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"> )
 <IMG SRC="images/forum/icons/icon_wink.gif">
 
 Chi voglia farselo da solo, basta che non apra il link.

euler_25 · 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">
 
 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">

euler_25 · 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:
 
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 ...tra gli altri numeri da 1 a p-1, potremo formare delle coppie tali che il loro prodotto dia a. 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 1/2(p-3) coppie di numeri diversi il cui prodotto è ≡ a mod p. Allora (p-1)! ≡ -a*a^(1/2(p-3)) ≡ -a^(1/2(p-1))...
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Ora, mi chiarisci un punto? Le (p-3)/2 coppie distinte di cui te riferisci nel tuo post non sono tutte della forma (xi, p-xi), con xi != x, per i = 1, 2, ..., (p-3)/2? <IMG SRC="images/forum/icons/icon_confused.gif">

Biagio · Messaggio da **Biagio** » 01 gen 1970, 01:33

anch\'io mi autocito:
 1)
 ecco come ho fatto io:
 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
 
 
 
 [ Questo Messaggio è stato Modificato da: Biagio il 11-02-2004 23:25 ]

euler_25 · Messaggio da **euler_25** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-02-11 23:23, Biagio wrote:
 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
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Uhm... Biagio, la tua dimostrazione potrebbe essere corretta, ma non posso accordarle incondizionatamente il mio placet! 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">
 
 P.S.: e poi un\'altra domanda, tanto per rompere i maroni... mi chiarisci quale condizione t\'assicura la consistenza della congruenza: g^((p-1)/2) ≡ -1 mod p. 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">
 
 EDIT: mi son levato dal letto con il pensiero! Biagio, sia ben chiaro, ché non vorrei essere frainteso. Lo statement che ho evidenziato è assolutamente corretto. 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"> [ Questo Messaggio è stato Modificato da: euler_25 il 12-02-2004 09:05 ]

Messaggio da **ma_go** » 01 gen 1970, 01:33

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

euler_25 · Messaggio da **euler_25** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-02-12 13:40, ma_go wrote:
 ii) se ti dico \"teorema di chebycheff\"? mi sputi in faccia, immagino! *
 comunque esiste (e non è difficile) una dimostrazione elementare...
 
 * il teorema di chebycheff afferma che tra n e 2n+2 esistono sempre due primi distinti, se non vado errando
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 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!!!
 
 P.S.: tanto per la cronaca, mi risulta cmq che la formulazione originale 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):
 
 Teorema di Chebichev: comunque fissato un n intero > 1, esiste sempre almeno un numero primo p tale che: n [ Questo Messaggio è stato Modificato da: euler_25 il 12-02-2004 14:37 ]

talpuz · Messaggio da **talpuz** » 01 gen 1970, 01:33

ok, ora tocca a me autocitarmi.. <IMG SRC="images/forum/icons/icon_biggrin.gif">
 
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 ogni numero a compreso tra 1 e p-1 ha un inverso nello stesso intervallo (cioè un numero b tale ab==1 mod p)
 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
 quindi 1*2*3*...*(p-2)==1 mod p
 moltiplicando per p-1 (che è ==-1 mod p) si ha la tesi
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>

Messaggio da **EvaristeG** » 01 gen 1970, 01:33

Non ho capito cosa tu voglia chiedere...cmq quello che intendevo è:
 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.
 Rimangono x e (p-x) che tra loro moltiplicati danno -a.
 Da cui i contazzi che seguono; in realtà non mi interessa minimamente che forma abbiano le coppie di fattori....

Biagio · Messaggio da **Biagio** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-02-12 02:26, euler_25 wrote:
 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...!
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 infatti, è un dettaglio
 
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-02-12 02:26, euler_25 wrote:
 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">
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 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.
 
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-02-12 02:26, euler_25 wrote:
 P.S.: e poi un\'altra domanda, tanto per rompere i maroni... mi chiarisci quale condizione t\'assicura la consistenza della congruenza: g^((p-1)/2) ≡ -1 mod p. 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">
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 questa è una proprietà dei generatori

euler_25 · 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...
 
 Problema iv): dimostrare che, comunque considerato un numero primo p > 2, esiste almeno un intero positivo 1 < g k !≡ 1 (mod p), per ogni k = 1, 2, ..., p-2.
 
 NOTA: è vietato ogni ricorso alla Teoria dei Gruppi... grazie!!! [ Questo Messaggio è stato Modificato da: euler_25 il 12-02-2004 22:34 ]

euler_25 · Messaggio da **euler_25** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-02-12 19:29, EvaristeG wrote:
 Non ho capito cosa tu voglia chiedere...cmq quello che intendevo è:
 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.
 Rimangono x e (p-x) che tra loro moltiplicati danno -a.
 Da cui i contazzi che seguono; in realtà non mi interessa minimamente che forma abbiano le coppie di fattori...
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Bene, avevo frainteso io, Evariste! Meglio così, adesso mi è tutto chiaro! <IMG SRC="images/forum/icons/icon_razz.gif">

euler_25 · Messaggio da **euler_25** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-02-12 19:23, talpuz wrote:
 ogni numero a compreso tra 1 e p-1 ha un inverso nello stesso intervallo (cioè un numero b tale ab==1 mod p)
 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
 quindi 1*2*3*...*(p-2)==1 mod p
 moltiplicando per p-1 (che è ==-1 mod p) si ha la tesi
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 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">
 
 Ché del resto... de gustibus non disputandum est! <IMG SRC="images/forum/icons/icon21.gif">