n|2^{n-1}+1 [Ammissione wc]

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Avatar utente
EUCLA
Messaggi: 771
Iscritto il: 21 apr 2005, 19:20
Località: Prato

n|2^{n-1}+1 [Ammissione wc]

Messaggio da EUCLA » 13 gen 2008, 22:17

Beh, a questo punto penso si possa proprio discuterne! :D

Beccatevi sto problemozzo! È fattibilissimo, anche se io per arrivare alla soluzione ho dovuto far passare un anno! :)

Determinare tutti gli interi positivi $ n $ tali che $ n\vert 2^{n-1}+1 $

Magari lasciamo divertire chi non ha provato...

rapportaureo
Messaggi: 124
Iscritto il: 18 feb 2007, 20:58

Messaggio da rapportaureo » 14 gen 2008, 13:42

io,sorprendendomi, ci ho messo 10 minuti..infatti dopo aver inviato i problemi, rivedendola,mi sono accorta che era totalmente assurda!!

Penso che sia ora di smettere di assumere strane sostanze prima di fare i problemi!! :lol: :lol: (poco da ridere in realtà)

Avatar utente
EUCLA
Messaggi: 771
Iscritto il: 21 apr 2005, 19:20
Località: Prato

Messaggio da EUCLA » 14 gen 2008, 14:01

Allora ritenta! :wink:

Jacobi
Messaggi: 227
Iscritto il: 08 mar 2007, 16:29

Messaggio da Jacobi » 14 gen 2008, 18:39

qst soluzione l'ho trovata in 10 minuti quindi nn so se e estta... cmq:

Ovviamente $ n $ nn puo essere pari, quindi sia $ n $ dispari e sia $ p $un suo fattore primo , allora $ n=pa $, da cui per ipotesi e':

$ 2^{ap-1} + 1 \equiv 0 {\pmod {ap}} \rightarrow 2^{ap} \equiv -2 \pmod p $
( piccolo teorema di fermat ) $ \rightarrow 2^a \equiv -2 \pmod p $
A questo punto possiamo supporre wlog che gcd(a;p) = 1, in quanto se cosi nn fosse potremmo levare altri fattori p ripetendo il processo di cui sopra. quindi per il piccolo teorema di fermat ( di nuovo ):

$ 2^a \equiv -2 \pmod p \rightarrow 2 \equiv -2 \pmod p \rightarrow p|4 $, ma $ p $ e' dispari quindi nn esiste p

Ne consegue che n=1 e' l'unica soluzione
MIND TORNA CON NOI

Avatar utente
EUCLA
Messaggi: 771
Iscritto il: 21 apr 2005, 19:20
Località: Prato

Messaggio da EUCLA » 14 gen 2008, 19:02

Jacobi ha scritto: $ 2^a \equiv -2 \pmod p \rightarrow 2 \equiv -2 \pmod p $
Mica vale sempre che $ 2^{a}\equiv 2 \pmod p $...

Pigkappa
Messaggi: 1208
Iscritto il: 24 feb 2005, 13:31
Località: Carrara, Pisa

Messaggio da Pigkappa » 14 gen 2008, 20:28

Ah, il caro vecchio metodo di fare i conti a caso e di fretta, sbagliandoli, trovando perciò un assurdo e risolvendo così il problema...

Avatar utente
angus89
Messaggi: 281
Iscritto il: 28 ott 2006, 10:12

Messaggio da angus89 » 14 gen 2008, 21:03

Allora...sottolineo il fatto che il mio è un tentativo e credo non copra proprio tutti i casi

Allora
$ \dispaystyle \\ n|2^{n-1} + 1 \\ 2^{n-1} + 1 = kn \\ 2^{n-1} = kn - 1 \\ $

moltiplichiamo per 2 entrambi i membri
$ \dispaystyle \\ 2^{n} = 2(kn - 1) $

ora
$ \dispaystyle \\ 2^{n}\equiv 2(kn - 1) \pmod 2 \\ 2^{n}\equiv 0 \pmod 2 \\ 2(kn - 1)\equiv 0 \pmod 2 \\ kn - 1 \equiv 0 \pmod 2 \\ k\equiv 1/n \pmod 2 \\ $

ma ciò è valido solo se n=1 dato che stiamo parlando di interi e k è un intero...
Spero di non aver sparato cavolate anche perchè ho trascritto tutto in fretta...
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui

Pigkappa
Messaggi: 1208
Iscritto il: 24 feb 2005, 13:31
Località: Carrara, Pisa

Messaggio da Pigkappa » 14 gen 2008, 21:06

angus89 ha scritto: $ 2(kn - 1)\equiv 0 \pmod 2 \\ kn - 1 \equiv 0 \pmod 2 \\ $
??

Avatar utente
EUCLA
Messaggi: 771
Iscritto il: 21 apr 2005, 19:20
Località: Prato

Messaggio da EUCLA » 14 gen 2008, 21:12

Ah, apparte riguardare quando dividere e quali fattori puoi togliere...tieni presente che stiamo parlando di congruenze e che se tu volessi in qualche modo togliere l'n dovresti moltiplicare per l'inverso di n ..che è intero.

Avatar utente
angus89
Messaggi: 281
Iscritto il: 28 ott 2006, 10:12

Messaggio da angus89 » 14 gen 2008, 21:48

Premetto di aver scritto tutto in fretta...
Mentre cenavo mi è proprio venuto in mente quello che ha detto Pigkappa...

Per rimediare bisogna fare un passo in dietro...va bè ripartiamo tanto è corto...
$ \dispaystyle n|2^{n-1}+1 $

pertanto
$ \dispaystyle \\ 2^{n-1}+1=nk \\ 2^{n-1}=nk-1 \\ $

fermiamoci qui e...
$ \dispaystyle \\ 2^{n-1} \equiv nk-1 \pmod 2 \\ 2^{n-1} \equiv 0 \pmod 2 \\ nk-1 \equiv 0 \pmod 2 \\ $

pertanto per ipotesi k è intero, n è intero, quindi lo sviluppo dell'ultima
$ \dispaystyle \\ k \equiv 1/n \pmod 2 \\ $
Che è giustificata solo per $ \dispaystyle n=1 $

...

sempre con l'augurio di aver sbagliato senza aver detto enormi cavolate... :D
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui

Avatar utente
salva90
Messaggi: 1314
Iscritto il: 19 ott 2006, 18:54
Località: Carrara

Messaggio da salva90 » 14 gen 2008, 21:51

angus89 ha scritto: pertanto per ipotesi k è intero, n è intero, quindi lo sviluppo dell'ultima
$ \dispaystyle \\ k \equiv 1/n \pmod 2 \\ $
Che è giustificata solo per $ \dispaystyle n=1 $
e qui erri :? in teoria dei numeri 1/n è l'invero di n, ossia quell'intero a tale che an vale uno modulo qualcosa...
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]

Avatar utente
Sesshoumaru
Messaggi: 87
Iscritto il: 13 dic 2007, 19:13
Località: Roma

Messaggio da Sesshoumaru » 15 gen 2008, 14:12

Tento la fortuna :lol:

Allora...
E' evidente che $ \displaystyle n $ dev'essere dispari (escludendo anche $ \displaystyle n=1 $, che è una soluzione ovvia). Dunque indichiamo $ \displaystyle n $ come $ \displaystyle 2k+1 $, con $ \displaystyle n>2 $.

Il problema diventa trovare gli interi $ \displaystyle k>0 $ tali che $ \displaystyle 2k+1|2^{2k}+1 $.

Abbiamo sicuramente che $ \displaystyle 2^{2k}-j \equiv 0 \pmod {2k} $, per un qualche $ \displaystyle j $ pari, poichè i multipli di $ \displaystyle 2k $ sono tutti pari e $ \displaystyle 2^{2k} $ è anch'esso pari.

E per ipotesi $ \displaystyle 2^{2k}+1 \equiv 0 \pmod {2k+1} $

Dunque esiste un intero $ \displaystyle a $ per cui $ \displaystyle a(2k)=2^{2k}-j $ e un intero $ \displaystyle b $ per cui $ \displaystyle b(2k+1)=2^{2k}+1 $.

Svolgiamo: $ \displaystyle 2^{2k}-2ak -j =0 $ e $ \displaystyle 2^{2k}-2bk -b +1 =0 $

Dunque $ \displaystyle 2^{2k}-2ak -j=2^{2k}-2bk -b +1 $, da cui $ \displaystyle -2ak -j = -2bk +1 $, e quindi $ \displaystyle 2k(b-a)=1+j $.
Questo è però un assurdo, poichè a sinistra abbiamo un numero pari, e a destra uno dispari.

Dunque non esistono $ \displaystyle k>0 $ tali che $ \displaystyle 2k+1|2^{2k}+1 $, e quindi l'unico valore cercato di $ \displaystyle n $ è $ \displaystyle n=1 $.

:roll: :D
[img]http://img65.imageshack.us/img65/2554/userbar459811cf0.gif[/img]

[i]"You have a problem with your brain: the left part has nothing right in it, and the right part has nothing left in it."[/i]

geda
Messaggi: 125
Iscritto il: 30 ott 2007, 12:03

Messaggio da geda » 15 gen 2008, 14:40

Sesshoumaru ha scritto:Tento la fortuna
Dunque $ \displaystyle 2^{2k}-2ak -j=2^{2k}-2bk -b +1 $, da cui $ \displaystyle -2ak -j = -2bk +1 $, e quindi $ \displaystyle 2k(b-a)=1+j $.
Questo è però un assurdo, poichè a sinistra abbiamo un numero pari, e a destra uno dispari.
Forse mi sono perso qualcosa ma...
$ \displaystyle 2^{2k}-2ak -j=2^{2k}-2bk -b +1 $, da cui $ \displaystyle -2ak -j = -2bk -b+1 $, e quindi $ \displaystyle 2k(b-a)=1+j-b $.

Poiché $ \displaystyle b $ è per forza dispari (vedi sopra nel tuo messaggio) il motivo dell'assurdità della tua conclusione cade.

Avatar utente
Sesshoumaru
Messaggi: 87
Iscritto il: 13 dic 2007, 19:13
Località: Roma

Messaggio da Sesshoumaru » 15 gen 2008, 14:46

geda ha scritto:
Sesshoumaru ha scritto:Tento la fortuna
Dunque $ \displaystyle 2^{2k}-2ak -j=2^{2k}-2bk -b +1 $, da cui $ \displaystyle -2ak -j = -2bk +1 $, e quindi $ \displaystyle 2k(b-a)=1+j $.
Questo è però un assurdo, poichè a sinistra abbiamo un numero pari, e a destra uno dispari.
Forse mi sono perso qualcosa ma...
$ \displaystyle 2^{2k}-2ak -j=2^{2k}-2bk -b +1 $, da cui $ \displaystyle -2ak -j = -2bk -b+1 $, e quindi $ \displaystyle 2k(b-a)=1+j-b $.

Poiché $ \displaystyle b $ è per forza dispari (vedi sopra nel tuo messaggio) il motivo dell'assurdità della tua conclusione cade.
Ecco, lo sapevo :cry: :lol:
[img]http://img65.imageshack.us/img65/2554/userbar459811cf0.gif[/img]

[i]"You have a problem with your brain: the left part has nothing right in it, and the right part has nothing left in it."[/i]

Avatar utente
salva90
Messaggi: 1314
Iscritto il: 19 ott 2006, 18:54
Località: Carrara

Messaggio da salva90 » 15 gen 2008, 14:55

Pigkappa ha scritto:Ah, il caro vecchio metodo di fare i conti a caso e di fretta, sbagliandoli, trovando perciò un assurdo e risolvendo così il problema...
eccone un altro :lol:
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]

Rispondi