facilissimo

[Valerio Capraro]

dimostrare che ogni intero positivo k non divide 2^k - 1

ciao

[Kroldar]

Caso 1 - k pari: $ 2^k - 1 $ si scompone in $ (2^(k/2) + 1)(2^(k/2) - 1) $ . $ (2^(k/2) + 1 $ non è divisibile per 2, mentre $ (2^(k/2) - 1 $ si scompone in modo analogo in $ (2^(k/4) + 1)(2^(k/4) - 1) $ . ripetendo il ragionamento all'infinito si arriva al caso $ (2^(k/k) + 1)(2^(k/k) - 1) $ ovvero 3*1 (deduciamo che il numero è dunque sempre divisibile per 3)
Caso 2 - k dispari: $ 2^k - 1 $ si scompone in $ (2-1)P(x) $ dove P(x) = $ 2^(k-1) + 2^(k-2) + ... + 1 $ di grado pari che ha solo coppie di soluzioni complesse coniugate

Spero di non aver commesso errori madornali

[Kroldar]

Caso 1 - k pari: $ 2^k - 1 $ si scompone in $ (2^(k/2) + 1)(2^(k/2) - 1) $ . $ 2^(k/2) + 1 $ non è divisibile per 2, mentre $ 2^(k/2) - 1 $ si scompone in modo analogo in $ (2^(k/4) + 1)(2^(k/4) - 1) $ . ripetendo il ragionamento all'infinito si arriva al caso $ (2^(k/k) + 1)(2^(k/k) - 1) $ ovvero 3*1 (deduciamo che il numero è dunque sempre divisibile per 3)
Caso 2 - k dispari: $ 2^k - 1 $ si scompone in $ (2-1)P(x) $ dove P(x) = $ 2^(k-1) + 2^(k-2) + ... + 1 $ di grado pari che ha solo coppie di soluzioni complesse coniugate

Spero di non aver commesso errori madornali

[Kroldar]

Scusami... avevo capito divisibile per 2. L'ho commesso eccome l'errore

[Kroldar]

vediamo di rettificare la cosa... se k è pari allora $ 2^k - 1 $ è dispari e dunque non può essere divisibile per un numero pari (ma abbiamo visto che è divisibile per 3); se invece k è dispari ed è numero primo, per il piccolo teorema di fermat segue che $ 2^k - 1 $ fa 1 modulo k e quindi non è divisibile per k. purtroppo non riesco a estendere la cosa nel caso di k dispari ma non primo... puoi darmi un aiuto?

[Valerio Capraro]

mmm... se ti potessi dare un aiuto significherebbe che io l'ho già risolto... e questo non è vero!!
Il problema sembra infatti meno banale di quello che sembra...

il tuo approccio è buono e porta anche ad una soluzione utilizzando la congettura di Goldbach nella formulazione "ogni numero dispari è somma di tre primi"!!!!!

Bah... vediamo un pò

ciao, ubermensch

[carlo23]

dimostrare che ogni intero positivo k non divide 2^k - 1

ciao

Sono riuscito un caso particolare

Il teorema è vero quando $k$ è una potenza di un numero primo, cioè $k=p^n$ con $p$ numero primo.
Infatti per il piccolo teorema di Fermat per ogni numero $a$ si ha

$a^p -= a mod p$

quindi

$2^p-=2 mod p$

e anche

$(2^p)^p -= 2^p -= 2 mod p$

isi dimostra facilmente per induzione che $2^(p^n) -= 2 mod p$ e quindi $2^(p^n)-1 -= 1 mod p$ ed è immediato che $p^n$ non divide $2^(p^n)-1$.

Complimenti a ubermensch che ha postato sto problema originale

[Kroldar]

molto bene... abbiamo fatto qualche passo avanti... ci rimane ora il caso più difficile, cioè k dispari dato dal prodotto di più numeri primi non tutti uguali tra loro

[carlo23]

Ho fatto alcuni progressi con la congettura di ubermensch riguardo $k>1$ che non divide mai $2^k-1$.
Pensavo di aspettare di dimostrare il caso generale, ma ho visto che sono ancora molto lontano, quindi posto
la dimostrazione di un altro caso particolare. Magari qualcuno leggendola riesce a dimostrare il caso generale.

Però prima riassumo un attimo i passi che abbiamo fatto e dove siamo arrivati:

$k>1$ non divide mai $2^k-1$ per

1) $k$ pari

2) $k$ numero primo

3) $k$ potenza di un numero primo

4) $k=pq$ dove $p$ e $q$ sono due numeri primi distinti

Dimostrazione del caso 4

La dimostrazione segue dal seguente:

Teorema (credo di Eulero)

Siano $p$ e $q$ due numeri primi tali che $p$ divide $2^q-1$, allora $p -= 1mod 2q$



Mettiamo che $k>1$ divida $2^k-1$, con $k=pq$ dove $p$ e $q$ sono due numeri primi tali che $p<q$.
Allora noi sappiamo che

$(2^p-1)^q -= 2^(pq)-1 -= 0 mod q$

e anche che


$(2^q-1)^p -= 2^(pq)-1 -= 0 mod p$

essendo $p$ un numero primo $a^s -= 0 mod p$ implica $a -= 0 mod p$ e quindi abbiamo che

$q$ divide $2^p-1$

$p$ divide $2^q-1$

adesso non ci resta che applicare il teorema di Eulero e otteniamo

$q -= 1 mod 2p$

$p -= 1 mod 2q$

dato che sia $p$ che $q$ sono >1 dalla prima e dalla seconda di queste ultime uguaglianze
si ricava rispettivamente

$q>2p$

$p>2q$

ma ciò e ovviamente impossibile e conclude la dimostrazione.


Rimane solo il caso più difficile: $k$ intero qualsiasi...