Sequenze di Mersenne 2 - una forte caratterizzazione

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Sequenze di Mersenne 2 - una forte caratterizzazione

Messaggio da edriv »

Sia $ ~ a_1,a_2,\ldots $ una sequenza di Mersenne, cioè una sequenza di interi positivi tale che:
$ ~ \mbox{gcd}(a_m,a_n) = a_{\mbox{gcd}(m,n)} $ per ogni m,n interi positivi.

Dimostrare che esiste una sequenza di interi positivi $ ~b_1, b_2,\ldots $ tale che per ogni n:
$ ~ \displaystyle a_n = \prod_{d \mid n} b_d $
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

tanto forte quanto banale...

Messaggio da HiTLeuLeR »

edriv ha scritto:Sia $ ~ a_1,a_2,\ldots $ una sequenza di Mersenne, cioè una sequenza di interi positivi tale che: $ ~ \mbox{gcd}(a_m,a_n) = a_{\mbox{gcd}(m,n)} $ per ogni m,n interi positivi. Dimostrare che esiste una sequenza di int. pos. $ ~b_1, b_2,\ldots $ t.c. per ogni n: $ ~ \displaystyle a_n = \prod_{d \mid n} b_d $
EDIT: va', che ci ripenso! :roll:
Ultima modifica di HiTLeuLeR il 28 mag 2007, 16:07, modificato 2 volte in totale.
albert_K
Messaggi: 182
Iscritto il: 10 set 2006, 19:34
Contatta:

Messaggio da albert_K »

Per me non è affatto banale!

Però $ b_{mn} = a_{mn}/(a_m \cdot a_n) $ sicuro che sia intero?

Però.. anche fosse $ b_{mn} = (a_m \cdot a_n)/a_{mn} $ mi pare che non funzioni :? ....
Dovrebbe essere sufficiente un controesempio con le successioni $ a_n = kn $ che, se l'ora tarda non mi fa dire scemate, sono di Mersenne.
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

albert_K ha scritto:Per me non è affatto banale! Però $ b_{mn} = a_{mn}/(a_m \cdot a_n) $ sicuro che sia intero?
Se $ m, n \in \mathbb{N}^+ $ e $ \gcd(m,n) = 1 $, allora nondimeno $ \gcd(a_m, a_n) = 1 $. Senonché $ \gcd(a_{mn}, a_m) = a_m $ e $ \gcd(a_{mn}, a_n) = a_n $. Dunque $ a_m \cdot a_n $ divide $ a_{mn} $. C'era comunque un errore - ho editato.
MindFlyer

Messaggio da MindFlyer »

HiTLeuLeR ha scritto:Se $ m, n \in \mathbb{N}^+ $ e $ \gcd(m,n) = 1 $, allora nondimeno $ \gcd(a_m, a_n) = 1 $.
Ma no, a me sembra che $ \gcd(a_m, a_n) = a_1 $, non $ 1 $.
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

... E siamo ancora a lunedì! :?
MindFlyer

Messaggio da MindFlyer »

Oggi invece è martedì!
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco »

E oggi è mercoledì...

Bello questo problema. Chi è la fonte?

Questa soluzione ripassa due teoremini che capita di usare poco spesso in ambito olimpico.

Fomula di inversione di Moebius: Sia $ \left( f_n \right)_{n \geqslant 1} $ una successione di numeri reali. Se la successione $ \left( g_n \right)_{n \geqslant 1} $ è definita da:

$ $g_n = \sum_{d \mid n} f_d $,

allora

$ $f_n = \sum_{d \mid n} \mu(d) g_{n/d} $,

dove $ \mu(n) $ è la funzione di Moebius, che vale $ 0 $, se $ n $ non è libero da quadrati; $ 1 $ se $ n $ è il prodotto di un numero pari [eventualmente 0] di primi distinti; $ -1 $ se $ n $ è il prodotto di un numero dispari di primi distinti.


Formula per il Minimo Comune Multiplo: Sia $ A $ un insieme non vuoto di numeri naturali positivi; indichiamo con $ (A) $ e $ [A] $ il MCD e il mcm degli elementi di $ A $ rispettivamente. Allora

$ $[A] = \prod_{B \subseteq A; B \neq \emptyset} (B)^{(-1)^{|B|+1}}. $


Questa si dimostra semplicemente con il PIE applicato agli insiemi con molteplicità dei divisori degli elementi di $ A $. Giusto per rendere intellegibile la formula, scrivo a mo' di esempio i casi con 2, 3, 4 elementi.

$ [a, b] = \frac{ a b }{ (a,b) } $

$ [a, b, c] = \frac{ a b c (a,b,c) }{ (a,b) (a,c) (b,c) } $

$ [a, b, c, d] = \frac{ a b c d (a,b,c) (a,b,d) (a,c,d), (b,c,d)}{ (a,b) (a,c) (b,c), (a,d), (b,d), (c,d) (a,b,c,d) } $

E veniamo alla soluzione.

Lemma 1: Se $ m \mid n $, allora $ a_m \mid a_n $.

Dim.: $ \left( a_m, a_n \right) = a_{(m,n)} = a_m $. []

Sol.: La Formula di Moebius, applicata ai logaritmi degli $ a $ e dei $ b $, ci dice che, affinché gli $ a_n $ verifichino la relazione $ a_n = \prod_{d \mid n} b_d $, deve essere

$ $b_n = \prod_{d \mid n} a_{(n/d)}^{\mu(d)} $. (1)

$ b_n $ è chiaramente un numero razionale. La nostra tesi è che sia anche intero.

Sia $ P $ l'insieme dei divisori primi di $ n $. Se $ Q \subseteq P $, indico con $ n/Q $ l'intero

$ \frac{n}{\prod_{p \in Q} p} $.

Lemma 2: $ ( n/{Q_1}, n/{Q_2} ) = n/(Q_1 \cup Q_2) $.

Dim: Ovvia. []

Applico la formula del mcm ai numeri $ a_{n/p} $, al variare di $ p \in P $:

$ $[a_{n/p}]_{p \in P} = \prod_{Q \subseteq P; Q \neq \emptyset} (a_{n/p})_{p \in Q} ^ {(-1)^{|Q|+1}} = \dots $

Per ipotesi, $ \left( a_n \right) $ è di Mersenne, quindi

$ $\dots = \prod_{Q \subseteq P; Q \neq \emptyset} a_{ (n/p)_{p \in Q} } ^ {(-1)^{|Q|+1}} = \dots $

Applico il Lemma 2:

$ $\dots = \prod_{Q \subseteq P; Q \neq \emptyset} a_{ n/Q } ^ {(-1)^{|Q|+1}} = \dots $

Infine, noto che, se $ d $ è un divisore di $ n $ libero da quadrati e $ Q $ è l'insieme dei suoi divisori primi, $ (-1)^{|Q|} = \mu \left( \prod_{p \in Q} p \right) = \mu(d) $; mentre se $ d $ è un divisore di $ n $ non libero da quadrati, ovviamente $ \mu(d) = 0 $.

Ne segue che:

$ $\dots = \prod_{d | n; d \neq n} a_{ n/d } ^ {-\mu(d)}. $

Ma allora la (1) diventa semplicemente:

$ $b_n = \frac{a_n}{[a_{n/p}]_{p \in P}} $.

Ora, per il Lemma 1, per ogni $ p \in P $, $ a_{n/p} \mid a_n $, quindi, in particolare anche il loro mcm deve dividere $ a_n $, perciò $ b_n $ è intero. []
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv »

Ah, ma alla fine l'avete risolto questo, mentre io ero al preIMO e quindi non me ne sono neanche accorto!

Molto elegante la soluzione di Marco.
A breve posto la mia, che è completamente diversa!
piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever »

Non mi sembra giusto che un problema abbia solo soluzioni pulite, per cui metto anche la mia (sullo stile della puntata precedente delle sequenze di Mersenne):

Supponiamo che per un certo valore di n, esiste una serie in cui si puo' fare la serie di b fino a $ b_{n-1} $ e poi ci si blocca.

Tra le serie per cui cio' accade, scelgo quella che minimizza il prodotto dei primi n termini.

Ora, per $ 1\le i\le n-1 $ si ha che $ b_i=1 $ altrimenti potrei porre $ b_i=1 $, dividere tutti gli $ a_{ki} $ per il $ b_i $ che c'era prima e ottenere una serie con prodotto minore (in cui, ovviamente, ancora non riesco a fare l'n-simo termine, perche', se i|n, ho diviso $ a_n $ tanto quanto ho diviso il prodotto dei b che non deve dividerlo, se $ i\nmid n $ non ho alterato nessuno dei 2).

Quindi la nostra negazione della tesi passa da cosi':

$ ~ \displaystyle \prod_{d \mid n} b_d \nmid a_nb_n $

a cosi':

$ 1\nmid a_n $
"Sei la Barbara della situazione!" (Tap)
Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv »

Figata! :o

Metto anche la mia: osserviamo che se
$ ~ a_n = \prod_{d\mid n} b_d $
e $ ~ a_n $ è una sequenza di Mersenne, allora $ ~ (b_i,b_j) \neq 1\Rightarrow i\mid j \lor j \mid i $.

Anzi, per ogni sequenza $ ~b_i $ con quest'ultima proprietà, $ ~ a_n = \prod_{d\mid n} b_d $ è una sequenza di Mersenne, noi vogliamo dimostrare il viceversa.

Supponiamo di avere già costruito la successione $ ~ b_i $ per tutti gli i che dividono strettamente n, e troviamo anche $ ~ b_n = \frac{a_n}{\prod_{d\mid n, d \neq n} b_d} $. Basta dimostrare che:
$ ~ \prod_{d\mid n, d \neq n} b_d \mid a_n $.
Ora, consideriamo il reticolo dei divisori stretti di n, e a ogni nodo d associamo $ ~ b_d $. Noi vorremmo che il prodotto di tutti i nodi divida $ ~ a_n $. Però sappiamo solo, ad esempio, che il prodotto di tutti i nodi di una catena divide $ ~ a_n $, questo perchè $ ~ d\mid n \Rightarrow a_d \mid a_n $.
Sappiamo anche che $ ~ (b_i,b_j) \neq 1\Rightarrow i\mid j \lor j \mid i $, questo vuol dire che, dato un primo p, i multipli di p in questo reticolo formano una catena. Ma quindi è finita. (la soluzione, non la catena, anzi, anche la catena)

Per ogni primo p che divide $ ~ a_n $, consideriamo tutti i b_i (con i che divide strettamente n) tali che p divide b_i, detto b_k il massimo di questi, per il lemma prima sono tutti divisori di k. (non tutti i divisori)
Quindi l'esponente di p che divide $ ~ \prod_{d\mid n, d \neq n} b_d $ è uguale all'esponente di p che divide $ ~ a_k $ che è minore o uguale all'esponente di p che divide a_n :)


Comunque wow, addirittura 3 soluzioni a due a due distinte!
Ultima modifica di edriv il 25 giu 2007, 21:50, modificato 1 volta in totale.
Simo_the_wolf
Moderatore
Messaggi: 1053
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf »

piever, uomo dalle poche parole...

sei sicuro che dividendo per $ b_i $ rimane ancora una sequenza di Mersenne? Non è così ovvio... Cioè sono sicuro che per te magari è ovvio ma magari bisognerebbe spenderci 2 parole :D
Anche spiegare cosa vuol dire per te che riesco a costruire la serie dei b fino a n-1... Guardo solo i primi n-1 termini di $ a_k $ o anche quelli dopo ?
piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever »

Spettacolare la soluzione di edriv
Simo_the_wolf ha scritto:sei sicuro che dividendo per $ b_i $ rimane ancora una sequenza di Mersenne?
Lol, segue facilmente dal fatto che 2 e' un generatore modulo 5^k...

A parte gli scherzi, dividendo tutti i multipli di i per una costante cosa succede?

Se x e y non sono multipli di i, allora (sia A' la sequenza A modificata):

$ (a'_x,a'_y)=(a_x,a_y)=a_{(x,y)}=a'_{(x,y)} $ (sostanzialmente non ho cambiato nulla)

Se x e' un multiplo di i, e y non lo e', allora:

$ (a'_x,a'_y)=(a_x,a_y)=a_{(x,y)}=a'_{(x,y)} $ (:P)

Ma forse qui servono alcune parole, direbbe il Lupo Pescarese.

Il gcd sicuramente non aumenta passando dalla serie originale a quella modificata. Diminuisce? No, perche, posto $ ((x,y),i)=g $ (solo per comodita' di notazione), abbiamo:

$ \displaystyle (a_{(x,y)},a'_i)=\prod_{d|g} b_d=a_g $ (ovviamente $ i\nmid y\Rightarrow i\nmid (x,y)\Rightarrow i\nmid ((x,y),i) $)

Quindi:

$ \displaystyle a_{(x,y)}|a_x\wedge a_i|a_x\Rightarrow \frac{a_{(x,y)}a_i}{a_g}|a_x\Rightarrow \frac{a_{(x,y)}a'_i}{a_g}|a'_x\Rightarrow a_{(x,y)}|a'_x $

Se invece sia x sia y sono multipli di i si ha:

$ \displaystyle (a'_x,a'_y)=(\frac{a_x}{b_i},\frac{a_y}{b_i})=\frac{a_{(x,y)}}{b_i}=a'_{(x,y)} $

Simo_the_wolf ha scritto:Anche spiegare cosa vuol dire per te che riesco a costruire la serie dei b fino a n-1... Guardo solo i primi n-1 termini di $ a_k $ o anche quelli dopo ?
Nono, basta che guardi i termini della serie fino al (n-1)-esimo. Posso ipotizzare che fino a quel punto riesco a costruire la serie dei b_i
"Sei la Barbara della situazione!" (Tap)
Avatar utente
wolverine
Messaggi: 59
Iscritto il: 11 nov 2007, 12:35

Messaggio da wolverine »

Non mi e' del tutto chiaro che dividendo tutti i termini di posto $ ki $ di una successione di Mersenne si ottenga ancora una successione di Mersenne. Ad esempio, se divido tutti i termini di posto $ 4k $ per $ a_4 $, lasciando gli altri inalterati, ottengo una successione con $ a'_4=1 $ e $ a'_2=a_2 $, e dunque non si ha $ (a'_4,a'_2)=a'_2 $ a meno che non si avesse gia' $ a_2=1 $.
Tuttavia l'argomento di piever mi sembra funzionare, basta fare le cose con ordine e dividere il piu' possibile: prima si dividono tutti i termini per $ a_1 $, poi tutti i termini di posto pari della successione $ a'_n $ per $ a'_2 $, poi tutti i termini di posto $ 3i $ della successione $ a''_n $ per $ a''_3 $, e cosi' via. In questo modo si dovrebbe ottenere effettivamente una successione di Mersenne con tutti i primi termini uguali ad 1, mediante riduzioni successive a partire da una qualunque successione di Mersenne data.
I'm the best there is at what I do. But what I do best isn't very nice.
piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever »

wolverine ha scritto:Non mi e' del tutto chiaro che dividendo tutti i termini di posto $ ki $ di una successione di Mersenne si ottenga ancora una successione di Mersenne.
Non ti e' chiaro perche' e' falso.
wolverine ha scritto:Tuttavia l'argomento di piever mi sembra funzionare.
Sospiro di sollievo, ogni tanto quando rivedo qualche mio vecchio post mi accorgo di aver scritto cose assurde...
wolverine ha scritto:basta fare le cose con ordine e dividere il piu' possibile: prima si dividono tutti i termini per $ a_1 $, poi tutti i termini di posto pari della successione $ a'_n $ per $ a'_2 $, poi tutti i termini di posto $ 3i $ della successione $ a''_n $ per $ a''_3 $, e cosi' via. In questo modo si dovrebbe ottenere effettivamente una successione di Mersenne con tutti i primi termini uguali ad 1, mediante riduzioni successive a partire da una qualunque successione di Mersenne data.
Nel post immediatamente precedente al tuo ho scritto una dimostrazione del perche' posso fare quello che ho fatto (ne ho scritte due a dire il vero, ma quella del generatore modulo 5 era una battuta...). Comunque anche il tuo sistema funziona...

ciaociao
"Sei la Barbara della situazione!" (Tap)
Rispondi