n non divide 2^n -1 per n>1
n non divide 2^n -1 per n>1
Se $ $n>1 $ intero, dimostrare che $ $n $ non divide $ $2^n-1 $
Appassionatamente BTA 197!
Si dovrebbe fare con "il più piccolo primo" almeno di non dir cavolate come mio solito... 
Ammettiamo che esista un tale $ n $. Allora $ 2^n \equiv 1 (\mod n) $.
Consideriamo la fattorizzazione in primi di n. $ \displaystyle n= p_1^{{\alpha}_1}\dots p_n^{{\alpha}_n} $ e supponiamo $ p_1<...<p_n $.
Per il TCR abbiamo che
$ 2^n\equiv 1 (\mod p_1^{\alpha_1}) $
$ \\ \dots \\ \dots \\ \dots \\ 2^n \equiv 1 (\mod p_n^{\alpha_n}) $
e quindi vale anche $ 2^n \equiv 1 (\mod p_1) $
($ p_1 $ è il più piccolo primo)
Abbiamo che $ \\2^{p-1} \equiv 1 (\mod p_1) $
$ 2^n \equiv 1 (\mod p_1) $
$ 2^{ord_{2}(p)}\equiv 1 (\mod p_1) $
Allora $ ord_{2}(p)|n , ord_{2}(p)|p-1 \rightarrow $
$ \rightarrow (ord_{2}(p), p-1)= q_1^{\beta_1}\dots q_n^{\beta_n}| q_1,...q_n<p_1 $
Allora $ n $ ha un divisore $ q $ (primo) che è minore di $ p_1\rightarrow $assurdo.
Ammettiamo che esista un tale $ n $. Allora $ 2^n \equiv 1 (\mod n) $.
Consideriamo la fattorizzazione in primi di n. $ \displaystyle n= p_1^{{\alpha}_1}\dots p_n^{{\alpha}_n} $ e supponiamo $ p_1<...<p_n $.
Per il TCR abbiamo che
$ 2^n\equiv 1 (\mod p_1^{\alpha_1}) $
$ \\ \dots \\ \dots \\ \dots \\ 2^n \equiv 1 (\mod p_n^{\alpha_n}) $
e quindi vale anche $ 2^n \equiv 1 (\mod p_1) $
($ p_1 $ è il più piccolo primo)
Abbiamo che $ \\2^{p-1} \equiv 1 (\mod p_1) $
$ 2^n \equiv 1 (\mod p_1) $
$ 2^{ord_{2}(p)}\equiv 1 (\mod p_1) $
Allora $ ord_{2}(p)|n , ord_{2}(p)|p-1 \rightarrow $
$ \rightarrow (ord_{2}(p), p-1)= q_1^{\beta_1}\dots q_n^{\beta_n}| q_1,...q_n<p_1 $
Allora $ n $ ha un divisore $ q $ (primo) che è minore di $ p_1\rightarrow $assurdo.
vi sottopongo una pseudo-dimostrazione induttiva, giusto per vedere quanto è delirante...
Non ho latex, quindi abbrevierò non divide con ND
La proprietà P in questione è che n ND 2^n - 1 per n>1
Se n è pari, allora è chiaro che n ND 2^n-1, essendo tale quantità dispari. Resta da dimostrare il caso n dispari
1) P vale per 3, poichè 3 ND 8-1=7 (però!)
2) per Hp induttiva, suppongo che n ND 2^n-1
3) dimostro che (n+1) ND (2^(n+1)-1)
beh, n è dispari, n+1 sarà pari, mentre 2^(n+1) -1 è dispari
Con ciò è dimostrato che P vale per ogni n naturale
Effetivamente mi pare che qualcosa non funzioni, aspetto risposte
enjoy!
Non ho latex, quindi abbrevierò non divide con ND
La proprietà P in questione è che n ND 2^n - 1 per n>1
Se n è pari, allora è chiaro che n ND 2^n-1, essendo tale quantità dispari. Resta da dimostrare il caso n dispari
1) P vale per 3, poichè 3 ND 8-1=7 (però!)
2) per Hp induttiva, suppongo che n ND 2^n-1
3) dimostro che (n+1) ND (2^(n+1)-1)
beh, n è dispari, n+1 sarà pari, mentre 2^(n+1) -1 è dispari
Con ciò è dimostrato che P vale per ogni n naturale
Effetivamente mi pare che qualcosa non funzioni, aspetto risposte
enjoy!
L'unica cosa che hai dimostrato è che la tesi è vera se n è pari.ummagumma ha scritto:vi sottopongo una pseudo-dimostrazione induttiva, giusto per vedere quanto è delirante...
Non ho latex, quindi abbrevierò non divide con ND
La proprietà P in questione è che n ND 2^n - 1 per n>1
Se n è pari, allora è chiaro che n ND 2^n-1, essendo tale quantità dispari. Resta da dimostrare il caso n dispari
1) P vale per 3, poichè 3 ND 8-1=7 (però!)
2) per Hp induttiva, suppongo che n ND 2^n-1
3) dimostro che (n+1) ND (2^(n+1)-1)
beh, n è dispari, n+1 sarà pari, mentre 2^(n+1) -1 è dispari
Con ciò è dimostrato che P vale per ogni n naturale
Effetivamente mi pare che qualcosa non funzioni, aspetto risposte
enjoy!
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...
Mi sembra che l'errore nel ragionamento sia quello che ho evidenziato...ummagumma ha scritto:vi sottopongo una pseudo-dimostrazione induttiva, giusto per vedere quanto è delirante...
Non ho latex, quindi abbrevierò non divide con ND
La proprietà P in questione è che n ND 2^n - 1 per n>1
Se n è pari, allora è chiaro che n ND 2^n-1, essendo tale quantità dispari. Resta da dimostrare il caso n dispari
1) P vale per 3, poichè 3 ND 8-1=7 (però!)
2) per Hp induttiva, suppongo che n ND 2^n-1
3) dimostro che (n+1) ND (2^(n+1)-1)
beh, n è dispari, n+1 sarà pari, mentre 2^(n+1) -1 è dispari
Con ciò è dimostrato che P vale per ogni n naturale
Effetivamente mi pare che qualcosa non funzioni, aspetto risposte
enjoy!
è già qualcosa 
..è chiaro nel punto 2) ipotizzo ciò che voglio dimostrare. Tra l'altro l'induzione non è proprio la strategia migliore per dimostrare che una proprietà non vale...magari ci si può provare 
forse la dimostrazione varrebbe se dimostrassi nel punto 3) che la P vale per n+2 (ovvero per ogni n dispari)
..è chiaro nel punto 2) ipotizzo ciò che voglio dimostrare. Tra l'altro l'induzione non è proprio la strategia migliore per dimostrare che una proprietà non vale...magari ci si può provare forse la dimostrazione varrebbe se dimostrassi nel punto 3) che la P vale per n+2 (ovvero per ogni n dispari)
capisco che è accanimento terapeutico, ma leggetela. Riprendiamo da qui
Inoltre, per assurdo suppongo che n+1 divida 2(2^n - 1) +1, risulterà dunque:
2(2^n - 1) +1 = k*(n+1) con k numero naturale, ovvero:
2(2^n - 1) +1 - 2^n - k +k*2^n + 2^n - k*2^n = k*n
Raccogliendo, si ha:
2(2^n - 1) - (2^n - 1) + k*(2^n - 1) + 2^n*(1-k) = k*n
(2^n - 1)*(1+k) + 2^n*(1-k) = k*n
per k pari, il primo membro è dispari, il secondo pari, quindi assurdo
per k dispari, il primo membro è pari, il secondo dispari, quindi assurdo
Nella mia sfida contro l'induzione, spero che la pseudo dimostrazione sia completa
ma leggetela. Riprendiamo da qui
Riscrivo 2^(n+1) - 1 come 2(2^n - 1) +1vi sottopongo una pseudo-dimostrazione induttiva, giusto per vedere quanto è delirante...
Non ho latex, quindi abbrevierò non divide con ND
La proprietà P in questione è che n ND 2^n - 1 per n>1
Se n è pari, allora è chiaro che n ND 2^n-1, essendo tale quantità dispari. Resta da dimostrare il caso n dispari
1) P vale per 3, poichè 3 ND 8-1=7 (però!)
2) per Hp induttiva, suppongo che n ND 2^n-1
3) dimostro che (n+1) ND (2^(n+1)-1)
Inoltre, per assurdo suppongo che n+1 divida 2(2^n - 1) +1, risulterà dunque:
2(2^n - 1) +1 = k*(n+1) con k numero naturale, ovvero:
2(2^n - 1) +1 - 2^n - k +k*2^n + 2^n - k*2^n = k*n
Raccogliendo, si ha:
2(2^n - 1) - (2^n - 1) + k*(2^n - 1) + 2^n*(1-k) = k*n
(2^n - 1)*(1+k) + 2^n*(1-k) = k*n
per k pari, il primo membro è dispari, il secondo pari, quindi assurdo
per k dispari, il primo membro è pari, il secondo dispari, quindi assurdo
Nella mia sfida contro l'induzione, spero che la pseudo dimostrazione sia completa
