Risolvendo il problema di Sylvester mi è venuto in mente questo: a cosa è congruo n! modulo n+1? Quel cosa indica un numero fra 0 e n.
<BR>Buona estate ci si risente a settembre
<BR>
da Sylvester
Moderatore: tutor
n! = n * (n-1) * (n-2) ... * 2 * 1 mod (n+1)
<BR>
<BR>applicando le congruenze ai fattori
<BR>
<BR>n! = (-1) * (-2) * (-3) ... *(-n) mod (n+1)
<BR>
<BR>se n è dispari la prima e la seconda espressione sono identiche ma a segni
<BR>discordi : dunque
<BR>
<BR>(2a+1)! = 0 mod (2a+2)
<BR>
<BR>e già mi sembra qualcosa...
<BR>
<BR>
<BR>applicando le congruenze ai fattori
<BR>
<BR>n! = (-1) * (-2) * (-3) ... *(-n) mod (n+1)
<BR>
<BR>se n è dispari la prima e la seconda espressione sono identiche ma a segni
<BR>discordi : dunque
<BR>
<BR>(2a+1)! = 0 mod (2a+2)
<BR>
<BR>e già mi sembra qualcosa...
<BR>
Se n+1 è primo, la cosa si riduce al teorema di Wilson, che afferma che (p-1)!=-1 mod p.
<BR>Questo teorema è dimostrabile proprio utilizzando il fatto che p è primo con ogni fattore di (p-1)! che per questo motivo ammete un inverso modulo p.
<BR>Distinguiamo duecasi per n+1 non primo.
<BR>Se n+1 si può scrivere come il prodotto di due numeri distinti(diversi da 1), n! è chiaramete congruo a 0 mod n+1.
<BR>Il caso in cui i due fattori siano uguali esce solo fuori se n+1=p^2 (se n+1 =k^2 con k non primo, posso prendere un fattore del primo k per spostarlo nel secondo ottenendo due numeri diversi) per questo caso ci devo pensare, anche se ci vedo un po\' d\'\"indeterminazione\" <IMG SRC="images/splatt_forum/icons/icon_smile.gif"><BR><BR><font size=1>[ Questo Messaggio è stato Modificato da: Gauss il 2002-07-01 23:12 ]</font>
<BR>Questo teorema è dimostrabile proprio utilizzando il fatto che p è primo con ogni fattore di (p-1)! che per questo motivo ammete un inverso modulo p.
<BR>Distinguiamo duecasi per n+1 non primo.
<BR>Se n+1 si può scrivere come il prodotto di due numeri distinti(diversi da 1), n! è chiaramete congruo a 0 mod n+1.
<BR>Il caso in cui i due fattori siano uguali esce solo fuori se n+1=p^2 (se n+1 =k^2 con k non primo, posso prendere un fattore del primo k per spostarlo nel secondo ottenendo due numeri diversi) per questo caso ci devo pensare, anche se ci vedo un po\' d\'\"indeterminazione\" <IMG SRC="images/splatt_forum/icons/icon_smile.gif"><BR><BR><font size=1>[ Questo Messaggio è stato Modificato da: Gauss il 2002-07-01 23:12 ]</font>
<html>
I can smile... and kill while i smile.
</html>
I can smile... and kill while i smile.
</html>
-
FrancescoVeneziano
- Site Admin
- Messaggi: 606
- Iscritto il: 01 gen 1970, 01:00
- Località: Genova
- Contatta:
Io dico che n!= -1 (n+1) se n+1 è primo (teorema di Wilson);
<BR>n!= 0 (n+1) se n+1 è composto diverso da 4;
<BR>3!= 2 (4)
<BR>
<BR>Il procedimento di Jack non è corretto perché de x = -x (x+1) non si può dedurre x=0, ma esiste anche la soluzione (x+1)/2, come nel caso n=3
<BR>
<BR>Supponiamo che n+1 non sia primo, e sia p^a q^b r^c… la sua fattorizzazione in primi; evidentemente (a*p)! è multiplo di p^a, (b*q) di q^b…
<BR>Supponiamo che p sia il primo per il quale il prodotto primo*esponente sia massimo, quindi (a*p)!=0 (n+1)
<BR>Se n>=a*p allora n!= 0 (n+1)
<BR>Risolviamo il caso in cui n+1 è potenza di un primo, infatti se p^a - 1>=a*p, a maggior ragione p^a q^b r^c… - 1>= a*p
<BR>
<BR>p^a - 1>=p*a con a>1 perché il numero non è primo.
<BR>Se p>=3 la disuguaglianza vale per tutti gli a>1
<BR>Se p=2, la disuguaglianza vale per a>2, ma non per a=2
<BR>Quindi l’unica eccezione è n+1=2^2 n=3
<BR>CaO (ossido di calcio)
<BR>
<BR>n!= 0 (n+1) se n+1 è composto diverso da 4;
<BR>3!= 2 (4)
<BR>
<BR>Il procedimento di Jack non è corretto perché de x = -x (x+1) non si può dedurre x=0, ma esiste anche la soluzione (x+1)/2, come nel caso n=3
<BR>
<BR>Supponiamo che n+1 non sia primo, e sia p^a q^b r^c… la sua fattorizzazione in primi; evidentemente (a*p)! è multiplo di p^a, (b*q) di q^b…
<BR>Supponiamo che p sia il primo per il quale il prodotto primo*esponente sia massimo, quindi (a*p)!=0 (n+1)
<BR>Se n>=a*p allora n!= 0 (n+1)
<BR>Risolviamo il caso in cui n+1 è potenza di un primo, infatti se p^a - 1>=a*p, a maggior ragione p^a q^b r^c… - 1>= a*p
<BR>
<BR>p^a - 1>=p*a con a>1 perché il numero non è primo.
<BR>Se p>=3 la disuguaglianza vale per tutti gli a>1
<BR>Se p=2, la disuguaglianza vale per a>2, ma non per a=2
<BR>Quindi l’unica eccezione è n+1=2^2 n=3
<BR>CaO (ossido di calcio)
<BR>
Wir müssen wissen. Wir werden wissen.
-
Antimateria
- Messaggi: 651
- Iscritto il: 01 gen 1970, 01:00
- Località: Vergate sul Membro
Per vedere una dimostrazione bella, furba, interessante, divertente ed appagante (sì, l\'ho scritta io), visitate <!-- BBCode Start --><A HREF="http://kayo.altervista.org/" TARGET="_blank">il sito di ReKaio</A><!-- BBCode End -->, andate sotto la voce \"numeri primi\", e ditemi cosa ne pensate.
<BR>Ciao!!![addsig]
<BR>Ciao!!![addsig]
-
Antimateria
- Messaggi: 651
- Iscritto il: 01 gen 1970, 01:00
- Località: Vergate sul Membro
Ok, visto che nessuno ha la minima voglia di sbattersi, riassumo qui brevemente la dimostrazione per il caso in cui n+1 è composto. Per non doverci portare appresso quel \"+1\", che rompe abbastanza le scatole, diciamo n+1=k. Sia dunque k un numero non primo, distinguiamo 2 sottocasi:
<BR>1) k non è un quadrato,
<BR>2) k è un quadrato.
<BR>Se non lo è, allora è divisibile per due interi a, b tali che 1<a<b<k=ab. Questi due interi compaiono come fattori nella formula di n!, quindi k divide n!, perché k=ab: in questo caso il resto è 0.
<BR>Se k è un quadrato, esiste un intero m tale che 1<m<k=m^2. Notiamo che, per k>4, si ha 2m<k. Quindi, sia m che 2m (e 2m>m perché m>0) compaiono nella formula di n!. Ne consegue che n! è divisibile per 2m^2=2k, quindi a maggior ragione è divisibile per k: anche qui il resto è 0. Rimane il caso k=4, che dà resto 3.
<BR>1) k non è un quadrato,
<BR>2) k è un quadrato.
<BR>Se non lo è, allora è divisibile per due interi a, b tali che 1<a<b<k=ab. Questi due interi compaiono come fattori nella formula di n!, quindi k divide n!, perché k=ab: in questo caso il resto è 0.
<BR>Se k è un quadrato, esiste un intero m tale che 1<m<k=m^2. Notiamo che, per k>4, si ha 2m<k. Quindi, sia m che 2m (e 2m>m perché m>0) compaiono nella formula di n!. Ne consegue che n! è divisibile per 2m^2=2k, quindi a maggior ragione è divisibile per k: anche qui il resto è 0. Rimane il caso k=4, che dà resto 3.