Mersenne alla graticola...

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

Dimostrare che non esiste alcun n intero > 1 tal che n divida 2<sup>n</sup> - 1.
<BR>
<BR>
<BR>\"God does Arithmetic.\" - Karl Friedrich Gauss
Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz »

sia p il più piccolo primo che divide n, cioè (n,p-1)=1 (n>1)
<BR>
<BR>per il teorema di bezout (se si scrive così) esistono interi r e s tali che
<BR>
<BR>r*n + (p-1)*s = 1
<BR>
<BR>supponiamo che 2^n - 1 == 0 (n)
<BR>
<BR>allora anche
<BR>
<BR>2^n - 1 == 0 (p)
<BR>
<BR>dunque
<BR>
<BR>2^n==1 (p)
<BR>
<BR>a questo punto
<BR>
<BR>2^1 = 2^(r*n + (p-1)*s=(2^n)^r * (2^(p-1))^s==1 (p)
<BR>
<BR>per i risultati precedenti, e per il piccolo teorema di fermat
<BR>
<BR>l\'ultima riga presenta chiaramente un assurdo ( 2==1 (p)), da cui deduciamo che 2^n - 1 non è divisibile per p, e dunque neanche per n
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

Deliziosa, anche se diversa dalla mia... Bene, rilancio!
<BR>
<BR>Provare che, se p è un primo di Wieferich, allora di certo non può essere un primo di Mersenne.
<BR>
<BR>
<BR>\"And now... ehmmm... a psycological question!\" - Alexandre M. Vinogràdov
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

<!-- 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-09-10 18:44, talpuz wrote:
<BR>Sia p il più piccolo primo che divide n, cioè (n,p-1)=1 (n>1). Per il teorema di bezout (se si scrive così) esistono interi r e s tali che:
<BR>
<BR>r*n + (p-1)*s = 1
<BR>
<BR>Supponiamo che 2^n - 1 == 0 (n). Allora anche 2^n - 1 == 0 (p); dunque: 2^n==1 (p). A questo punto:
<BR>
<BR>2^1 = 2^(r*n + (p-1)*s=(2^n)^r * (2^(p-1))^s==1 (p)
<BR>
<BR>per i risultati precedenti, e per il piccolo teorema di fermat. L\'ultima riga presenta chiaramente un assurdo ( 2==1 (p)), da cui deduciamo che 2^n - 1 non è divisibile per p, e dunque neanche per n.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Ehm... deliziosa un bel paio di palle! Così com\'è, la tua soluzione proprio non va, Talpa, ci ho riflettutto un po\' sotto la doccia... Chiedo scusa, ma la fretta deve avermi un tantinello annebbiato. Il problema deve quindi ritenersi NON ANCORA RISOLTO! Se - fatto poco probabile - non dovesse riuscirti di comprenderne da solo le ragioni, beh... sarò ben lieto di evidenziarti il vizio logico celato dietro le tue argomentazioni. Ciao!
<BR>
<BR>
<BR>\"Fate l\'amore con il sapore.\" - la tv!!!
positrone
Messaggi: 40
Iscritto il: 01 gen 1970, 01:00
Località: mondo

Messaggio da positrone »

provo io(senza molte speranze).
<BR>Anzitutto vediamo che n non può dividere (2 ^n)-1 se n è pari,quindi ci rimane solo il caso in cui n è dispari.
<BR>Siccome n è dispari,allora n=2p+1,se chiamiamo k il quoziente della divisione (2^n)-1/n otteniamo l\'equazione 2^(2p)=k(2p+1)+1,allora per il piccolo teorema di fermat abbiamo che 2^2p==1mod(2p+1),allora 2(2^2p)==2mod(2p+1),di conseguenza non esiste un equazione del genere.
<BR>c.v.d.
Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll »

<!-- 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-09-11 10:34, positrone wrote:
<BR>allora per il piccolo teorema di fermat abbiamo che 2^2p==1mod(2p+1)
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Questo vale se 2p+1 è primo, non semplicemente dispari<BR><BR>[ Questo Messaggio è stato Modificato da: Boll il 11-09-2004 10:57 ]
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

Sì, è come dice Boll! Supponendo che n sia un dispari intero > 1, si ha che: 2<sup>n-1</sup> = 1 mod n se n è un numero primo. Viceversa, se n è composto, non è garantito che l\'anzidetta congruenza risulti soddisfatta, quantunque sia noto (teorema di Cipolla) ch\'esistono infiniti interi positivi n > 1 tali che n sia composto e nondimeno: 2<sup>n-1</sup> = 1 mod n. Si tratta dei cosiddetti \"pseudoprimi in base 2\". Son certo poi che avrete già sentito parlare, e almeno un milione di volte, dei mirabilissimi \"numeri di Carmichael\", per i quali vi rimando al solito sito di \"mathworld\". Forza, dunque, dateci sotto per sbrogliare questa misera matassa!
<BR>
<BR>
<BR>\"E adesso la pubblicità!\" - Claudio Baglioni, plagiando Maurizio Costanzo Show
Avatar utente
talpuz
Moderatore
Messaggi: 873
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da talpuz »

ok, come mi fa giustamente (e meticolosamente) notare il buon euler, gli interi previsti dal teorema di bezout possono essere anche negativi...
<BR>
<BR>in questo passaggio
<BR>
<BR>2^1 = 2^(r*n + (p-1)*s=(2^n)^r * (2^(p-1))^s
<BR>
<BR>potrebbero quindi esserci dei problemi...
<BR>
<BR>per disfarsene, basta innanzitutto sostituire 2^n==1 (p) e 2^(p-1)==1 (p), la prima ricavata in precedenza, la seconda è il piccolo th di fermat
<BR>
<BR>(in realtà c\'è anche da dire che deve essere p=/= 2 per applicare fermat.. del resto se p=2, allora n è pari, e non può dividere 2^n -1, che è dispari)
<BR>
<BR>a questo punto ci ritroviamo con
<BR>
<BR>2^1 = 2^(r*n + (p-1)*s=(2^n)^r * (2^(p-1))^s==(1)^r * (1)^s (p)
<BR>
<BR>e qui basta ricordare che se k è coprimo con p, k^(-1) (p) è semplicemente l\'inverso moltiplicativo di k modulo p, ovvero l\'intero h compreso tra 1 e p-1 tale che h*k==1 (p)
<BR>
<BR>supponiamo ad esempio quindi che r sia positivo e s negativo, s=-q, q>0
<BR>
<BR>(1)^r * (1)^s== 1 * [(1)^(-1)]^q (p) e a questo punto basta notare che l\'inverso moltiplicativo di 1 è semplicemente 1, e le conclusioni del mio post precedente rimangono valide
<BR>
[img:18oeoalk]http://www.narutolegend.it/char_img/Sasuke.jpg[/img:18oeoalk]
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

<!-- 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-09-11 15:01, Boll wrote:
<BR>Provo anch\'io apostare una sol al problema di Euler, ben sapendo che sarò ricoperto di insulti
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Un po\' te le vai cercando, siamo onesti con noi stessi, su...
<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-09-11 15:01, Boll continued:
<BR>Notazioni utilizzate: ==/== non è congruo
<BR>
<BR>Dobbiamo dimostrare che:
<BR>2^n - 1==/==0 (mod n) per nessun n>1
<BR>ora, per tutti i pari ciò è ovvio, dimostriamolo per n dispari:
<BR>per una nota affinità 2^n - 1 si può scrivere come
<BR>
<BR>sum[k=0,n-1](2^k)= 2^(n-1)+2^(n-2)+...+2+1
<BR>
<BR>fra i primi n-1 termini della sommatoria non è possibili che ve ne siano due che hanno la stessa congruenza mod n perchè ciò implicherebbe.
<BR>2^k==2^h (mod n)
<BR>2^k-2^k==0 (mod n) non possibile per n dispari [...]
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>A parte gli orrori ortosintattici... com\'è questa storia? Sentite un po\', prendere a colpi di badile i minorenni è un reato giuridicamente perseguibile, vero? Uffa... e mi spiegate allora come si fa a raddrizzargli la capa? Non di certo imboccandogli caramelline e chupa-chups...
<BR>
<BR>
<BR>\"Dio salvi il salvabile!\" - HiTLeuLeR
Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll »

Chiedo umilmente pietà, nella foga non mi ero accorto dell\'imperdonabile errore.
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)
positrone
Messaggi: 40
Iscritto il: 01 gen 1970, 01:00
Località: mondo

Messaggio da positrone »

Boiata,cancello tutto,
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: positrone il 11-09-2004 17:49 ]
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

Cosa?! Implori pietà? Baaah... Rimboccati le maniche, piuttosto, e mantieni lo sguardo ritto e il capo teso! La tua giovanissima età è più che sufficiente per giustificare le tue defaillances, senza che tu debba invocare esplicitamente il \"perdono\" dell\'opinione pubblica. La mia enfasi è puramente coreografica, lo sai!
<BR>
<BR>
<BR>\"Esiste una categoria di sogni che hanno un diritto tutto particolare di essere definiti ipocriti e che mettono a dura prova il tentativo degli uomini di conquistarsi la felicità!\" - Sigmund Freud, da \"L\'interpretazione dei sogni\"
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

<!-- 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-09-11 17:42, positrone wrote:
<BR>Boiata, cancello tutto.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Spero vivamente che tu faccia per dire! Ah, quand\'anche non fosse stato chiaro... il messaggio precedente era diretto a Boll. Vale!!!
<BR>
<BR>
<BR>\"Post coitum omne animal triste.\" - saggezza antica<BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 11-09-2004 18:12 ]
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

<!-- 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-09-11 15:08, talpuz wrote:
<BR>[...] Gli interi previsti dal teorema di bezout possono essere anche negativi...In questo passaggio:
<BR>
<BR>2^1 = 2^(r*n + (p-1)*s=(2^n)^r * (2^(p-1))^s
<BR>
<BR>potrebbero quindi esserci dei problemi... Per disfarsene, basta innanzitutto sostituire 2^n==1 (p) e 2^(p-1)==1 (p), la prima ricavata in precedenza, la seconda è il piccolo th di fermat. [...] A questo punto ci ritroviamo con:
<BR>
<BR>2^1 = 2^(r*n + (p-1)*s=(2^n)^r * (2^(p-1))^s==(1)^r * (1)^s (p)
<BR>
<BR>e qui basta ricordare che se k è coprimo con p, k^(-1) (p) è semplicemente l\'inverso moltiplicativo di k modulo p, ovvero l\'intero h compreso tra 1 e p-1 tale che h*k==1 (p)
<BR>
<BR>supponiamo ad esempio quindi che r sia positivo e s negativo, s=-q, q>0
<BR>
<BR>(1)^r * (1)^s== 1 * [(1)^(-1)]^q (p) e a questo punto basta notare che l\'inverso moltiplicativo di 1 è semplicemente 1, e le conclusioni del mio post precedente rimangono valide
<BR>
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>A meno che tu non voglia alzare un tantinello il regime della discussione e portarti a ragionare modulo p su elementi del campo razionale, temo che la tua soluzione, così come si presenta, evidenzi ancora qualche \"punto oscuro\"! Tento perciò, sinteticamente, di ricostruire il tuo ragionamento, riempiendo alcuni vuoti logici che, con elegante nonchalance, ti sei lasciato dietro nella tua folle corsa verso la gloria e il successo ad ogni costo [prrrrrr]! Prego le Muse e il Parnaso e gli dei dell\'Olimpo tutti di volermi assistere in questa mia epica impresa... e chiedo a te, Talpo, di usarmi misericordia, qualora dovessi spararle un po\' troppo grosse. Del resto, anch\'io sono qui per imparare!
<BR>
<BR>Come giustamente osservato da più parti, possiamo supporre n intero dispari > 1, e ammettere per assurdo che sia: 2<sup>n</sup> = 1 mod p, ove p rappresenta (nella notazione del buon Talpuz) il più piccolo dei divisori primi naturali di n. E allora, essendo D(n, p-1) = 1, esistono r ed s in Z, con r*s < 0, tali che: r*n + s*(p-1) = 1, in accordo con il lemma di Bezout. Giusto per fissare le idee, ammettiamo r < 0 ed s > 0 (il caso duale è perfettamente analogo).
<BR>
<BR>Dacché p è coprimo con 2<sup>n</sup>: 2<sup>n</sup> = 1 mod p ==> inv(2<sup>n</sup>) = 1 mod p, ove inv(-) denota qui l\'inverso aritmetico modulo p di un generico intero coprimo con p. E allora, nondimeno: [inv(2<sup>n</sup>)]<sup>|r|</sup> = 1 mod p ==> [In base ad una nota proprietà degli inversi aritmetici] ==> inv(2<sup>n*|r|</sup>) = 1 mod p. D\'altro canto, per il teorema di Euler-Fermat: 2<sup>p-1</sup> = 1 mod p, e dunque: 2<sup>(p-1)*s</sup> = 1 mod p ==> inv(2<sup>n*|r|</sup>)*2<sup>(p-1)*s</sup> = 1 mod p.
<BR>
<BR>Orbene, Talpo... nell\'identità modulare così ottenuta, \"analoga\" alla relazione finale da te indicata, tutte le quantità coinvolte stanno evidentemente in Z. Mi diresti orsù, di grazia, in che modo ti riesce dunque d\'identificare, e non solo formalmente (= dal punto di vista \"notazionale\"!!!), l\'inverso aritmetico modulo p di 2<sup>n*|r|</sup>, che è un numero INTERO, con l\'inverso moltiplicativo in Q di 2<sup>n*|r|</sup>, che è invece un numero razionale ma non un intero? Se vuoi operare in termini modulari su oggetti che non siano gli interi \"ordinari\", beh... cerca almeno di non usarti troppa leggerezza!
<BR>
<BR>EDIT: quasi dimenticavo! Nell\'attesa di ricevere eventuali chiarificazioni dal nostro amico Talpuz, direi che il problema può ritenersi ancora IRRISOLTO!
<BR>
<BR>
<BR>\"Varda ca vegnu \'docu e ti stimperu nu tumpuluni ca ti fazzu e \'vidi sa finisci mi ti \'lisci a curcia chi cazzati...\" - una specie di \"africani\"<BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 11-09-2004 21:13 ]
positrone
Messaggi: 40
Iscritto il: 01 gen 1970, 01:00
Località: mondo

Messaggio da positrone »

Rilancio(la stessa soluzione poi cancellata).
<BR>Consideriamo n dispari e non primo,e chiamiamolo 2p+1,scriviamo 2^(2p+1)come 2(2^2p),dobbiamo dimostrare che non può esserci 2( 2^2p)==1mod(2p+1). Possiamo allora vedere che non può esserci 2^2p==p+1mod(2p+1),
<BR>infatti per i dispari che finiscono per 3,5e9 dovremmo avere2^2p=2q,dove q è un numero dispari,mentre per i dispari che finiscono per 1 e 7 dovremmo avere che 2^2p è un numero dispari,perchè p+1 è pari. Di conseguenza non può esistere una tale equazione.
Bloccato