Pagina 1 di 2

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

Inviato: 13 gen 2008, 22:17
da EUCLA
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...

Inviato: 14 gen 2008, 13:42
da rapportaureo
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à)

Inviato: 14 gen 2008, 14:01
da EUCLA
Allora ritenta! :wink:

Inviato: 14 gen 2008, 18:39
da Jacobi
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

Inviato: 14 gen 2008, 19:02
da EUCLA
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 $...

Inviato: 14 gen 2008, 20:28
da Pigkappa
Ah, il caro vecchio metodo di fare i conti a caso e di fretta, sbagliandoli, trovando perciò un assurdo e risolvendo così il problema...

Inviato: 14 gen 2008, 21:03
da angus89
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...

Inviato: 14 gen 2008, 21:06
da Pigkappa
angus89 ha scritto: $ 2(kn - 1)\equiv 0 \pmod 2 \\ kn - 1 \equiv 0 \pmod 2 \\ $
??

Inviato: 14 gen 2008, 21:12
da EUCLA
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.

Inviato: 14 gen 2008, 21:48
da angus89
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

Inviato: 14 gen 2008, 21:51
da salva90
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...

Inviato: 15 gen 2008, 14:12
da Sesshoumaru
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

Inviato: 15 gen 2008, 14:40
da geda
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.

Inviato: 15 gen 2008, 14:46
da Sesshoumaru
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:

Inviato: 15 gen 2008, 14:55
da salva90
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: