Sequenze di Mersenne

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

Sequenze di Mersenne

Messaggio da edriv » 23 apr 2007, 17:17

Una sequenza di interi positivi $ ~ a_1,a_2,\ldots $è detta "sequenza di Mersenne" se, per ogni i,j interi positivi:
$ ~ \mathrm{gcd}(a_i,a_j) = a_{\mathrm{gcd}(i,j)} $

Esempi di sequenze di Mersenne sono $ ~ a^n-1 $, l'identità, la sequenza di Fibonacci.

Dimostrare che, per ogni intero positivo k, il prodotto dei primi k termini della sequenza divide il prodotto di qualsiasi k termini consecutivi.

In realtà definizione e teorema valgono in un qualsiasi anello euclideo

piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Re: Sequenze di Mersenne

Messaggio da piever » 25 apr 2007, 19:28

Uhm, supponiamo che l'enunciato sia falso per determinati valori k e j.

sia $ A=\{ a_1,\dots , a_n,\dots \} $ una sequenza di mersenne.

sia $ P_a $ l'insieme dei primi tali che $ v_p(a_1\dots a_k)>v_p(a_{j+1}\dots a_{j+k}) $

per ogni $ p \in P_a $ chiamiamo $ f(p) $ il minimo $ m $ tale che $ p|a_m $

sia $ q $ l'elemento di $ P_a $ che minimizza $ f(q) $ e sia $ g(A)=f(q) $ (NB: questa funzione e' definita solo sulle sequenze che falsificano la tesi per i j e k fissati in precedenza).

Io prendo la sequenza che massimizza $ g(A) $ e la chiamo A.

Poniamo $ f(q)=m $ e $ v_{q}(a_m)=e $

Ora, siccome $ a_m $ e' il primo ad essere diviso da $ q $, $ q $ divide tutti e soli gli elementi con un indice multiplo di m. Ovviamente li divide con esponente $ \ge e $

Siccome, per una proprieta' della floor function, tra j+1 e j+k ci sono almeno tanti multipli di m quanti tra 1 e k, se dividiamo tutti gli elementi con indice multiplo di m per $ q^e $ ottenendo una nuova sequenza di mersenne che chiamo $ B=\{ b_1,\dots , b_n,\dots \} $ sicuramente continuiamo ad avere $ b_1\dots b_k\nmid b_{j+1}\dots b_{j+k} $ ma ora $ g(B)>m $, assurdo.

In realtà questa dimostrazione vale in qualsiasi anello aristotelico, a patto di tradurla in greco antico (cosa che tra l'altro la renderebbe piu' comprensibile)



EDIT: quasi dimenticavo:

corollario: $ n\choose k $ e' intero per qualsiasi $ n\geq k \in\mathbb{N} $

corollario 2: buon Balkan
"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 » 25 apr 2007, 20:42

Wow, bella dimostrazione!

La mia era la stessa roba più o meno, scritta meno elegantemente:
In breve, tra $ ~ a_1,\ldots,a_k $ mettiamo che ci sono $ ~ c_n,c_{n-1},\ldots,c_1 $ elementi la cui valutazione p-adica è rispettivamente n,...,1. Allora si vede facilmente che in $ ~ a_{j+1}, \ldots, a_{j+k} $ ci sono almeno $ ~ c_n,c_n+c_{n-1},\ldots,c_n+c_{n-1} + \ldots + c_1 $ elementi che sono multipli rispettivamente di $ ~ p^n,p^{n-1}, \ldots, p $, da cui seguirà in qualche modo la tesi.

Interessante il corollario!
In effetti un altro modo per enunciare il problema è: "definiamo un mersenne-binomiale su una sequenza di Mersenne $ ~a_n $ come
$ \dislaystyle {n \choose k} = \frac{a_na_{n-1}\cdots a_{n-k+1}}{a_1a_2\cdots a_k} $ allora questo è sempre intero"

Rispondi