Principio di induzione?

Fai una domanda Tutte le categorie

24 lug 2014, 20:56

Ciao ragazzi mi aiutate?
Devo dimostrare che $2^n - 1$ non è sempre un numero primo, come posso fare?
$P(1) = 2^1 - 1 = 1$
$P(2) = 2^2 - 1 = 3$
$P(3) = 2^3 - 1 = 7$
$P(4) = 2^4 - 1 = 15 ( falsa )$
OK questa è una dimostrazione ma non posso tutte le volte provare tutti i valori giusto? quindi come si fa?

Risposte

garnak.olegovitc1

24 lug 2014, 19:05

"ignorante":
Ciao ragazzi mi aiutate?
Devo dimostrare che $2^n - 1$ non è sempre un numero primo, come posso fare?

quello che devi (di)mostrare è che $$\exists n \in \Bbb{N}(2^n-1 \notin \Bbb{P})$$ ed è quello che hai fatto, ovvero hai trovato un $n \in \Bbb{N}$ tale che $2^n-1 \notin \Bbb{P}$

Hai dimostrato!! Se vuoi farla più complicata puoi provare per assurdo e considerare il caso per $n=4$ come un controesempio..

P.S.= Come vedi l'induzione serve a poco (per certi aspetti hai usato una sorta di induzione empirica dalla quale però devi generalizzare/formalizzare un po meglio il ragionamento), preciso che $\Bbb{P}=\text{insieme dei numeri primi}$...

Sk_Anonymous

24 lug 2014, 19:19

Ma mettiamo caso che l' $n$ fosse stato il 10 000 esimo numero per dimostrarlo cosi sarebbe stato troppo lungo, possibile non ci sia un metodo più veloce?

garnak.olegovitc1

24 lug 2014, 19:35

« Frustra fit per plura quod fieri potest per pauciora. »

P.S.= Comunque sono sbadato, devi sapere che $1 \notin \Bbb{P}$...

@melia

24 lug 2014, 19:57

Potresti vederla così: se n è pari puoi indicarlo con $n=2h$, allora $2^n -1= 2^(2h)-1$, che è una differenza di quadrati e la puoi scrivere $2^(2h)-1 = (2^h -1)(2^h+1)$, per $h>=2$ si ha che $2^(2h)-1$ è un numero composto. Quindi ottieni un numero composto ogni volta che n è pari e maggiore di 4.