OliForum Matematico

Se $ $n>1 $ intero, dimostrare che $ $n $ non divide $ $2^n-1 $

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.

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!

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!

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!

Mi sembra che l'errore nel ragionamento sia quello che ho evidenziato...

è 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)

capisco che è accanimento terapeutico, ma leggetela. Riprendiamo da qui

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)

Riscrivo 2^(n+1) - 1 come 2(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

Per k dispari, il secondo membro è dispari

-> ma quindi stai supponendo n dispari, di nuovo, lo stai dimostrando solo per n+1 pari!!!

ok..ci rinuncio, al max si potrebbe cercare di mettere in evidenza 2^n -1 in qualke modo e sfruttare la 2)

p.s. in problemi simili di TdN eviterò l'induzione...

ummagumma ha scritto:ok..ci rinuncio, al max si potrebbe cercare di mettere in evidenza 2^n -1 in qualke modo e sfruttare la 2)

Trovo molto interessante la tua dimostrazione...
dhai, non mollare...

In realtà il problemino vale per due consecutivi generici, non solo 1 e 2...

Cioè per $ n>1 $, $ n $ non divide $ (x+1)^n-x^n $

magari per parecchi era banale, però io l'ho letto stamani