Disuguaglianza facile ma istruttiva

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
Pixel
Messaggi: 79
Iscritto il: 23 feb 2005, 16:16
Località: Trento

Disuguaglianza facile ma istruttiva

Messaggio da Pixel » 04 set 2005, 23:54

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} $
P. Andrea

scaccomatto
Messaggi: 2
Iscritto il: 01 set 2005, 12:17
Località: Milano

Messaggio da scaccomatto » 05 set 2005, 12:19

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... :)

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 05 set 2005, 17:00

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) $.

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 05 set 2005, 19:51

scaccomatto ha scritto: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
Messaggi: 565
Iscritto il: 01 gen 1970, 01:00
Località: Terra degli Shura (pisa)
Contatta:

Messaggio da ReKaio » 05 set 2005, 19:56

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

parrebbe anche iniettiva :p
_k_

Avatar utente
info
Messaggi: 903
Iscritto il: 01 gen 1970, 01:00

Messaggio da info » 08 set 2005, 08:45

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!

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 08 set 2005, 12:12

scaccomatto ha scritto:$ 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.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Avatar utente
Pixel
Messaggi: 79
Iscritto il: 23 feb 2005, 16:16
Località: Trento

Messaggio da Pixel » 08 set 2005, 12:49

Beh che dire...scusate il ritardo :oops:

Comunque la mia soluzione è uguale a quella di info.

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

Ciao
P. Andrea

Rispondi