n|2^{n-1}+1 [Ammissione wc]
n|2^{n-1}+1 [Ammissione wc]
Beh, a questo punto penso si possa proprio discuterne!
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...
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...
-
- Messaggi: 124
- Iscritto il: 18 feb 2007, 20:58
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
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
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...
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
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...
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...
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
e qui erri in teoria dei numeri 1/n è l'invero di n, ossia quell'intero a tale che an vale uno modulo qualcosa...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 $
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]
- Sesshoumaru
- Messaggi: 87
- Iscritto il: 13 dic 2007, 19:13
- Località: Roma
Tento la fortuna
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 $.
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 $.
[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]
[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]
Forse mi sono perso qualcosa ma...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.
$ \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.
- Sesshoumaru
- Messaggi: 87
- Iscritto il: 13 dic 2007, 19:13
- Località: Roma
Ecco, lo sapevogeda ha scritto:Forse mi sono perso qualcosa ma...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.
$ \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.
[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]
[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]