Pagina 1 di 1
potenze di 2 per un numero primo
Inviato: 07 feb 2008, 16:45
da angus89
Allora...
Credo che questo problema sia abbastanza semplice ma non riesco ad andare avanti...
Allora...si vuole dimostrare che se $ \dispaystyle 2^{n}-1 $ è un numero primo allora $ \dispaystyle n $ è necessariamente un numero primo...
Allora...
E' facile dimostare che$ \dispaystyle n $non può essere un numero pari (diverso da 2) perchè in tal caso sarebbe
$ \dispaystyle \\ n=2k \\
2^{2k}-1=(2^{k}-1) \cdot (2^{k}+1) $
Pertanto è evidente che nel caso $ \dispaystyle n $ sia un numero pari allora $ \dispaystyle 2^{n}-1 $ è scomponibile, pertanto non può essere primo...
Faccio notare un'altra cosa...
$ \dispaystyle 2^{n}-1 $ altro non è che una serie geometrica
$ \dispaystyle 2^{n}-1 = 1+2^{2}+2^{3}+...+2^{n-1} $
Non sò quanto può essere utile...
Io mi sto cimentando...
Sarebbe interessante vedere se n primo implica o meno $ \dispaystyle 2^{n}-1 $primo...e dimostare...
Inviato: 07 feb 2008, 17:03
da pic88
Puoi anche dimostrare che se n è composto, 2^n-1 è composto, perché è differenza di potenze ad indice comune. Cioè, scomporre 2^n-1 come (2-1)(serie geometrica) non aiuta perché 2-1=1, però se n=hk allora...
Ovviamente n primo non implica 2^n-1 primo, perché 2^11-1=2047=89*23 mi pare.
Inviato: 07 feb 2008, 17:44
da hydro
penso che
qui tu possa trovare qualcosa di interessante a proposito della questione...
Inviato: 07 feb 2008, 17:54
da angus89
PER CHI VUOLE CONTINUARE A CIMENTARSI NEL PROBLEMA NON LEGGA QUESTO POST
(mi riferisco soprattutto a chi non è molto pratico di tdn dato che credo ci sia un modo molto semplice per arrivare alla dimostrazione, chissà magari il mio)
Per gli altri...accetto correzioni ma non ironia o cose simili...al limite evitate di postare...
Allora...il ragionamento è questo...
Per prima cosa ci accertiamo che esistano numeri primi che abbiano la forma $ \dispaystyle 2^{n}-1 $...
$ \dispaystyle \\
n=5 \\
2^{5}-2=31 $
31 è primo.
C'è un teorema che afferma se esiste un numero primo con una determinata forma allora ne esistono infiniti con la stessa forma...in questo caso con la forma $ \dispaystyle 2^{n}-1 $
Nel post precedente abbiamo dimostrato che $ \dispaystyle n $ deve essere dispari.
Pertanto ammettiamo che $ \dispaystyle n $ non sia primo, ma risulti il prodotto di due numeri (non per forza primi).
$ \dispaystyle \\
2^{n}-1 \\
n=k \cdot h $
Questi due numeri non possono essere entrambi pari perchè genererebbero un numero pari.
Non possono essere uno pari e uno dispari perchè genererebbero un numero pari.
Pertanto questi due numeri devono essere entrami dispari...
Pertanto sarebbe più corretto affermare che
$ \dispaystyle \\
2^{n}-1 \\
n=(2k+1) \cdot (2h+1) \\
2^{(2k+1) \cdot (2h+1)}-1 $
A questo punto ricorriamo alla differenza di potenze dispari, o per chi la vuol vedere in un altro modo, alla sommatoria di una serie geometrica.
$ \dispaystyle \\
x^{n}-1=1+x+x^{2}+...+x^{n-1} $
Nel nostro caso abbiamo:
$ \dispaystyle \\
2^{(2k+1) \cdot (2h+1)}-1 \\
t=2^{2k+1} \\
t^{2h+1}-1=(t-1) \cdot (1+t+t^{2}+...+t^{2h})
$
Effettuato il cambio di variabile torniamo alla principale
$ \dispaystyle \\
t=2^{2k+1} \\
$
$ \dispaystyle \\
2^{(2k+1) \cdot (2h+1)}-1 =(2^{2k+1}-1) \cdot (1+2^{2k+1}+2^{2(2k+1)}+ $...$ \dispaystyle \\+2^{2h(2k+1)}) $
Pertanto è evidente che se $ \dispaystyle n $ non è primo allora
$ \dispaystyle 2^{n}-1 $
è scomponibile, quindi non è primo.
Allora deve essere $ \dispaystyle n $ primo affinche $ \dispaystyle 2^{n}-1 $ sia primo
Inviato: 07 feb 2008, 18:10
da alexba91
angus89 ha scritto:PER CHI VUOLE CONTINUARE A CIMENTARSI NEL PROBLEMA NON LEGGA QUESTO POST
(mi riferisco soprattutto a chi non è molto pratico di tdn dato che credo ci sia un modo molto semplice per arrivare alla dimostrazione, chissà magari il mio)
Per gli altri...accetto correzioni ma non ironia o cose simili...al limite evitate di postare...
Allora...il ragionamento è questo...
Per prima cosa ci accertiamo che esistano numeri primi che abbiano la forma $ \dispaystyle 2^{n}-1 $...
$ \dispaystyle \\
n=5 \\
2^{5}-2=31 $
31 è primo.
C'è un teorema che afferma se esiste un numero primo con una determinata forma allora ne esistono infiniti con la stessa forma...in questo caso con la forma $ \dispaystyle 2^{n}-1 $
Nel post precedente abbiamo dimostrato che $ \dispaystyle n $ deve essere dispari.
Pertanto ammettiamo che $ \dispaystyle n $ non sia primo, ma risulti il prodotto di due numeri (non per forza primi).
$ \dispaystyle \\
2^{n}-1 \\
n=k \cdot h $
Questi due numeri non possono essere entrambi pari perchè genererebbero un numero pari.
Non possono essere uno pari e uno dispari perchè genererebbero un numero pari.
Pertanto questi due numeri devono essere entrami dispari...
Pertanto sarebbe più corretto affermare che
$ \dispaystyle \\
2^{n}-1 \\
n=(2k+1) \cdot (2h+1) \\
2^{(2k+1) \cdot (2h+1)}-1 $
A questo punto ricorriamo alla differenza di potenze dispari, o per chi la vuol vedere in un altro modo, alla sommatoria di una serie geometrica.
$ \dispaystyle \\
x^{n}-1=1+x+x^{2}+...+x^{n-1} $
Nel nostro caso abbiamo:
$ \dispaystyle \\
2^{(2k+1) \cdot (2h+1)}-1 \\
t=2^{2k+1} \\
t^{2h+1}-1=(t-1) \cdot (1+t+t^{2}+...+t^{2h})
$
Effettuato il cambio di variabile torniamo alla principale
$ \dispaystyle \\
t=2^{2k+1} \\
$
$ \dispaystyle \\
2^{(2k+1) \cdot (2h+1)}-1 =(2^{2k+1}-1) \cdot (1+2^{2k+1}+2^{2(2k+1)}+ $...$ \dispaystyle \\+2^{2h(2k+1)}) $
Pertanto è evidente che se $ \dispaystyle n $ non è primo allora
$ \dispaystyle 2^{n}-1 $
è scomponibile, quindi non è primo.
Allora deve essere $ \dispaystyle n $ primo affinche $ \dispaystyle 2^{n}-1 $ sia primo
non sono un esperto di tdn, anzi sonoa nch io come te all inizio, pero se posso dire la mia, secondo me il tuo ragionamento è corretto ed è anche bella come dimostrazione.(avevo fatto il tuo stesso ragionamento)
Inviato: 07 feb 2008, 19:23
da Jacobi
premetto che nn ho letto la discussione...
per dimostrare il risultato basta notare che se n e nn primo, allora n=ab, con a e b diversi da n ed 1, quindi $ 2^n-1 = 2^{ab}-1 = (2^a)^b-1^b $ e poiche $ x-y|x^k-y^k $abbiamo che$ 2^a-1|2^n-1 $ quindi $ 2^a-1 $ e un fattore nn banale di $ 2^n-1 $, ergo nn e primo ( per n composto )
Inviato: 07 feb 2008, 19:28
da pic88
angus89 ha scritto:
C'è un teorema che afferma se esiste un numero primo con una determinata forma allora ne esistono infiniti con la stessa forma...
Che teorema è?
Inviato: 07 feb 2008, 19:29
da Carlein
Ho un osservazione banalerrima da fare e una domanda:l'osservazione è che dal fattarello delle progressioni geometriche consegue che per qualsiasi altro numero x intero maggiore di 2 allora $ x^n-1 $ con n maggiore di 1 non è mai primo(non mi linciate lo so che è banale ma solo per completezza l'ho messa
).La domanda è ma quel teorema che dice angus che se un numero primo si può scrivere in una forma allora ne esistono infiniti in tale forma è vero? se consideriamo la semplice funzione kn con k intero positivo primo e n variabile nei naturali essa darà un primo soltanto quando n=1.Sono sicuro di aver frainteso quello che diceva angus e aspetto correzioni...
Ciao
Inviato: 07 feb 2008, 19:29
da angus89
Jacobi ha scritto:premetto che nn ho letto la discussione...
per dimostrare il risultato basta notare che se n e nn primo, allora n=ab, con a e b diversi da n ed 1, quindi $ 2^n-1 = 2^{ab}-1 = (2^a)^b-1^b $ e poiche $ x-y|x^k-y^k $abbiamo che$ 2^a-1|2^n-1 $ quindi $ 2^a-1 $ e un fattore nn banale di $ 2^n-1 $, ergo nn e primo ( per n composto )
praticamente è la mia dimostrazione in due righe...
Inviato: 09 feb 2008, 15:58
da EvaristeG
No Carlein, quel teorema non esiste.
Inviato: 09 feb 2008, 16:39
da angus89
No...allora...mi sono espresso male io scusate...volevo dire che per alcune forme è dimostrabile...
Nel senso è dimostrabile ad esempio che esistono infiniti primi che hanno la forma $ \dispaystyle 4x-1 $ (se volete posto la dimostrazione)
Oppure è dimostrabile che ci sono infiniti numeri primi nella forma $ \dispaystyle 2^{n}-1 $...ecc ecc
Tipo come l'altro post che ho aperto...chiedo di dimostrare che esistono infiniti primi nella forma $ \dispaystyle 6k-1 $
Inviato: 09 feb 2008, 16:47
da FrancescoVeneziano
angus89 ha scritto:... è dimostrabile che ci sono infiniti numeri primi nella forma $ \dispaystyle 2^{n}-1 $
No, non è nota una dimostrazione di questo fatto. I primi di quella forma si chiamano primi di Mersenne, ne sono noti 44 fino ad oggi, ed è congetturato che siano infiniti ma non c'è ancora una dimostrazione.
Inviato: 09 feb 2008, 16:58
da angus89
FrancescoVeneziano ha scritto:angus89 ha scritto:... è dimostrabile che ci sono infiniti numeri primi nella forma $ \dispaystyle 2^{n}-1 $
No, non è nota una dimostrazione di questo fatto. I primi di quella forma si chiamano primi di Mersenne, ne sono noti 44 fino ad oggi, ed è congetturato che siano infiniti ma non c'è ancora una dimostrazione.
caspio...ora lo so...ero convinto fossero infiniti...