Disuguaglianza facile ma istruttiva

[Pixel]

Sia $ d(n) $ la funzione che ad ogni $ n\in \mathbb{N} $ associa il numero dei suoi divisori, dimostrare che:

$ d(2^n-1) \geq d(n) $ $ \forall n\in \mathbb{N} $

[scaccomatto]

Esprimiamo $ n=p_1 p_2...p_i $ con i vari p numeri primi non necessariamente diversi.
Allora
$ 2^n-1=2^{p_1 p_2...p_i}-1=(2^{p_1 p_2...p_{i-1}})^{p_i}-1 $
che si può scomporre come
$ (2^{n/p_i}-1)(2^{(n/p_i)(p_i-1)}+2^{(n/p_i)(p_i-2)}...+2+1) $
in cui il secondo fattore è sicuramente >1.
Applicando più volte lo stesso procedimento sul primo fattore, si ottiene un fattore maggiore di 1 di $ 2^n-1 $ per ogni fattore primo di n; se tutti i fattori ottenuti sono primi, $ d(2^n-1)=d(n) $, altrimenti $ d(2^n-1)>d(n) $.
Suggerimenti sono molto ben accetti: è un po' che visito il forum ma è la prima volta che provo a inviare una soluzione...

[HiTLeuLeR]

Lemma: sia $ a $ un naturale $ \geq 2 $. E allora, per ogni $ n \in\mathbb{N} $ ed ogni $ p\in\mathfrak{P} $ t.c. $ p \nmid (a-1) $: $ \displaystyle d\!\left(\frac{a^{p^n} - 1}{a-1}\right)\! \geq n+1 $.

Dim.: per induzione su $ n $, sfruttando la moltiplicatività della funzione $ d(\cdot) $ e il fatto che, nelle ipotesi del lemma: $ \displaystyle\gcd\!\left(\frac{a^{p^n} - 1}{a-1},\frac{a^{p^{n+1}} - 1}{a^{p^n}-1}\right)\! = 1 $, e inoltre $ \displaystyle \frac{a^{p^{n+1}} - 1}{a^{p^n}-1}> 1 $ e $ d(p^{n+1}) = n+2 $.

La soluzione: segue dal lemma precedente, ragionando per induzione sul numero dei divisori primi distinti di $ n $, e ricordando che, se $ \prod_{i=1}^r p_i^{\alpha_i} $ è la scomposizione canonica euclidea di un generico intero $ n \geq 2 $, ove $ p_1, p_2, \ldots, p_r $ sono primi naturali a due a due distinti ed $ \alpha_i \in\mathbb{N}_0 $, per ogni $ i = 1, 2, \ldots, r $, allora $ d(n) = \prod_{i=1}^r (1 + \alpha_i) $.

[HiTLeuLeR]

Esprimiamo $ n=p_1 p_2...p_i $ con i vari p numeri primi non necessariamente diversi. Allora $ 2^n-1=2^{p_1 p_2...p_i}-1=(2^{p_1 p_2...p_{i-1}})^{p_i}-1 $, che si può scomporre come $ (2^{n/p_i}-1)(2^{(n/p_i)(p_i-1)}+2^{(n/p_i)(p_i-2)}...+2+1) $, in cui il secondo fattore è sicuramente >1.

Applicando più volte lo stesso procedimento sul primo fattore, si ottiene un fattore maggiore di 1 di $ 2^n-1 $ per ogni fattore primo di n; se tutti i fattori ottenuti sono primi, $ d(2^n-1)=d(n) $, altrimenti $ d(2^n-1)>d(n) $.

Non funziona, mi spiace! Lascerò tuttavia di buon grado che sia Pixel a spiegartene il perché. Nel frattempo, tu prova a pensare (in mezzo al resto...) a quel che accade quando due primi della sequenza $ p_1, p_2, \ldots, p_i $ risultano uguali fra loro...

[ReKaio]

$ \psi: (\mathbb N,|) \rightarrow (\mathbb N,|) $ dove $ \psi(n)=2^n-1 $

parrebbe anche iniettiva :p

[info]

Ma scaccomatto non voleva osservare che se:

a | n --> (2^a -1) | (2^n -1)

mi pare sufficiente per rispondere (corrispondenza biunivoca di parte dei fattori), sbaglio?

Ciao!

[Marco]

$ 2^n-1= $ [...] $ = (2^{n/p_i}-1)(2^{(n/p_i)(p_i-1)}+2^{(n/p_i)(p_i-2)}...+2^{(n/p_i)}+1) $

Ciao ScaccoMatto e benvenuto tra i matematti del Forum. Per essere un primo post non sembra davvero male. Continua così! Non ascoltare quello zuccone di Hit e cerchiamo di completare la tua dimostrazione.

(intanto nota: ho fatto una piccola correzione alla tua formula).

C'è un piccolo problema infatti da risolvere: come si lega il numero dei divisori con il numero dei fattori primi (contati con molteplicità, quello che tu hai chiamato $ i $) di $ n $.

In sostanza, che cosa hai dimostrato? Hai provato che $ 2^n-1 $ si scompone in $ i $ fattori, non necessariamente primi.

Il fatto cattivo è che i numeri con $ i $ fattori primi non hanno tutti lo stesso numero di divisori. Prova ad esempio con 4 e 6. Entrambi hanno 2 fattori primi (4 = 2x2; 6 = 2x3). Ma il primo ha solo 3 divisori (1,2,4), mentre il secondo ne ha 4 (1,2,3,6).

Per sfruttare la tua idea ti suggerisco queste due ulteriori:

- il numero di divisori aumenta, se i fattori sono distinti (HINT: analogia: anagrammi con ripetizione...)
- c'è un modo per fare sì che i fattori "lunghi" che trovi via via scomponendo siano tutti diversi tra loro? (HINT: riesci a scegliere il $ p_i $ in modo che risultino, ad esempio, decrescenti? Anzi no HINT ancora più figo: scrivi i fattori lunghi in base 2. E' possibile che due di essi risultino uguali?)

@Info: Il tuo trucco funziona ed è probabilmente la soluzione più elegante che esista. Naturalmente non posso sapere che cosa avesse in mente Scacco con la sua dimostrazione, ma siccome dice "ripeto il ragionamento", suppongo voglia intendere che ha ottenuto un fattore lungo, che è maggiore di 1, e un fattore corto, che è di nuovo della forma "potenza di 2 meno 1", che però ha un fattore in meno. Ripete il ragionamento e rifattorizza il fattore corto.

Alla fine quindi, togliendo un fattore primo per volta, dopo i passi si ritrova il fattore corto che diventa 1 e tutti i fattori lunghi che ha generato fino a quel momento. Se prova che sono distinti, ad esempio, ha fatto.

Oppure si potrebbe tentare di dimostrarlo per induzione su i.

"per i = 0 è ovvio: n=1 e bla bla...

se i>0, allora isolo un fattore lungo e resto con un 2^n-1 che, per hp induttiva ha più divisori di bla bla. Perciò 2^n-1 ha almeno tot divisori. Ma i divisori di n sono quelli di n/p, ecc..."

Boh, provate un po' a vedere se funziona...

Ciao. M.

[Pixel]

Beh che dire...scusate il ritardo

Comunque la mia soluzione è uguale a quella di info.

Notate che il problema si può facilmente generalizzare!!!

Ciao