sui minimi comuni multipli e primi..

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

sui minimi comuni multipli e primi..

Messaggio da jordan » 21 set 2009, 18:49

Mostrare che $ \displaystyle \text{lcm}(1,2,\ldots,n)=\text{lcm}\left(\binom{n}{1},\binom{n}{2},\ldots,\binom{n}{n}\right) $ se e solo se $ n+1\in \mathbb{P} $.
The only goal of science is the honor of the human spirit.

eli9o
Messaggi: 106
Iscritto il: 14 mag 2008, 19:43

Messaggio da eli9o » 25 set 2009, 13:22

Se nessuno ha qualcosa in contrario, riprovo a farmi del male :lol:

Osservazione 1: la successione 1,2,1,4,1,2,1,8... indica l'esponente di un primo $ p $ nella fattorizzazione dei più piccoli (non volevo dire primi) interi positivi multipli di $ p $.
Allora la somma dei primi $ n $ termini di questa successione è maggiore o uguale della somma dei primi $ m $ termini più i primi $ n-m $ termini (ovviamente con n>m).

Mostriamo che se $ n=2k-1 $ (con $ k>1 $) e $ 2^a||LHS, 2^b||RHS $ allora $ a>b $.
Per trovare $ b $ consideriamo $ \displaystyle\frac{n-1}{2}\frac{n-3}{4}\cdots\frac{n-2c+1}{2c} $ al variare ci c. Consideriamo l'esponente del fattore 2 in ogni numeratore. Se è presente $ a $ allora ai lati partono due successioni 1,2,1,4... come quella di prima che ha somma minore o uguale della successione lunga $ c-1 $. Ma al denominatore c'è la successione lunga $ c $ che ha somma strettamente maggiore ci quella lunga $ c-1 $.
$ b\leq a+ $(somma termini successione lunga c-1)-(somma termini successione lunga c) quindi $ b<a $. Se al numeratore non c'è a, tanto meglio!

Analogamente si mostra che se $ n=pk-1 $ (con $ k>1 $)e $ p^a||LHS, p^b||RHS $ allora $ a>b $.

Mi rendo conto che è scritta malissimo ma credo che l'essenziale ci sia. Lascio per ora l'altra freccia e completo eventualmente dopo pranzo che ho fame :)
Hypotheses non fingo

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 25 set 2009, 19:20

Mostriamo che se $ \displaystyle~n=p-1,~p\in\mathbb{P} $ allora $ \displaystyle~\forall q<p,~q\in\mathbb{P} $, posto $ \displaystyle~a=\max\{r:q^r<p\} $, esiste un binomiale divisibile per $ \displaystyle~q^a $ (che è la massima potenza di $ \displaystyle~q $ nel primo l.c.m.): a tale scopo poniamo anche $ \displaystyle~b=\max\{s:sq^a<p\} $. Si tratta di massimizzare ora $ \displaystyle~\binom{p-1}{i}=\sum_{j>0}\left(\left\lfloor\frac{p-1}{q^j}\right\rfloor-\left\lfloor\frac{p-i-1}{q^j}\right\rfloor-\left\lfloor\frac{i}{q^j}\right\rfloor\right) $, cioè di minimizzare $ \displaystyle~\sum_{j>0}\left(\left\lfloor\frac{p-i-1}{q^j}\right\rfloor+\left\lfloor\frac{i}{q^j}\right\rfloor\right) $. Ora intuitivamente il minimo si realizza con $ \displaystyle~i=p-bq^a $ (infatti così $ \displaystyle~p-i-1 $ è appena prima di una bella potenza di $ \displaystyle~q $ e $ \displaystyle~i $ è poco pericoloso). E infatti abbiamo $ \displaystyle~\sum_{j>0}\left\lfloor\frac{p-i-1}{q^j}\right\rfloor=\sum_{j>0}\left\lfloor\frac{bq^a-1}{q^j}\right\rfloor $$ \displaystyle~=bq^{a-1}-1+bq^{a-2}-1+\ldots+bq^0-1=b\cdot\frac{q^a-1}{q-1} $ e $ \displaystyle~\sum_{j>0}\left\lfloor\frac{i}{q^j}\right\rfloor=\sum_{j>0}\left\lfloor\frac{p-bq^a}{q^j}\right\rfloor=\sum_{j>0}-bq^{a-1}-\ldots-bq^0=\sum_{j>0}\left\lfloor\frac{p}{q^j}\right\rfloor-b\cdot\frac{q^a-1}{q-1} $. Dunque $ \displaystyle~\sum_{j>0}\left(\left\lfloor\frac{p-i-1}{q^j}\right\rfloor+\left\lfloor\frac{i}{q^j}\right\rfloor\right)=\sum_{j>0}\left\lfloor\frac{p}{q^j}\right\rfloor+a=\sum_{j>0}\left\lfloor\frac{p-1}{q^j}\right\rfloor+a $ (dato che $ \displaystyle~q\nmid p $).. Dunque in $ \displaystyle~\binom{p-1}{i} $ ci sono esattamente $ \displaystyle~a $ fattori $ \displaystyle~q $. D'altra parte non ci può essere un $ \displaystyle~i $ tale che $ \displaystyle~\binom{p-1}{i}=\frac{(p-1)(p-2)\cdots(p-i)}{i!} $ abbia più di $ \displaystyle~a $ fattori $ \displaystyle~q $, infatti $ \displaystyle~\upsilon_q((p-1)(p-2)\cdots(p-i))\le a+\sum_{j>0}\left\lfloor\frac{i-1}{q^j}\right\rfloor\le a+\sum_{j>0}\left\lfloor\frac{i}{q^j}\right\rfloor $ da cui $ \displaystyle~\upsilon_q\left(\binom{p-1}{i}\right)\le a $. Quindi se $ \displaystyle~n+1 $ è primo i due l.c.m. sono uguali. Rimane de provare il viceversa. Notiamo che vale $ \displaystyle~\upsilon_q\left(\mathop{\text{lcm}}\left(\binom{n}{1},\binom{n}{2},\ldots,\binom{n}{n}\right)\right)< a,~\forall q|n+1 $ (con $ \displaystyle~q $ primo e $ \displaystyle~a $ in funzione di $ \displaystyle~q $ e definito sempre allo stesso modo), infatti $ \displaystyle~\upsilon_q\left(\binom{n}{i}\right)=\upsilon_q(n(n-1)\cdots(n-i+1))-\upsilon_q(i!) $$ \displaystyle~\le a+\sum_{j>0}\left\lfloor\frac{i-q}{q^j}\right\rfloor-\upsilon_q(i!)< a+\sum_{j>0}\left\lfloor\frac{i}{q^j}\right\rfloor-\upsilon_q(i!)=a $. Dunque se $ \displaystyle~n+1 $ non è primo i due l.c.m. sono diversi, da cui il contronominale che se i due l.c.m. sono uguali $ \displaystyle~n+1 $ è primo..
Se c'è qualche passaggio non chiaro non esitate a chiedere..

@eli9o: non ho la forza di leggere la tua dimostrazione :lol: , forse ho scritto le stesse cose..
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 27 set 2009, 13:10

@Jordan: hai una soluzione più decente a questo problema?
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 08 ott 2009, 16:36

@eli: si, anche se la prima parte avresti dovuta dimostrarla, alla fine l'altra implicazione e gli altri casi in cui n+1 è composto, le idee ci sono, ma diciamo che devi imparale a scriverle un po meglio :wink:
@kn: sono finalmente riuscito a leggere la tua (in realtà ci ho messo meno di quella di eli XD), e si, direi che fila, very good :o
Ne scrivo anche un'altra, sperando che sia di vostro gradimento:

Lemma. Per ogni $ n \in \mathbb{N}_0 $ vale $ \displaystyle \text{lcm}\left(\binom{n}{1},\binom{n}{2},\ldots,\binom{n}{n}\right)=\frac{\text{lcm}(1,2,\ldots,n,n+1)}{n+1} $ (chiaramente il problema ne è un corollario).
Fissato $ p \in \mathbb{P} $, sia $ h_p(\cdot):\mathbb{N}_0 \to \mathbb{N}_0 $ quell'intero non negativo tale che $ p^{h_p(x)} \le x < p^{h_p(x)+1} $, e siano $ (\alpha_p,\beta_p,\gamma_p) \in \mathbb{N}^3 $ tali che: $ \alpha_p:=\upsilon_p\left(\displaystyle (n+1)\text{lcm}\left(\binom{n}{1},\binom{n}{2},\ldots,\binom{n}{n}\right)\right) $, $ \beta_p:=\upsilon_p\left(\text{lcm}(1,2,\ldots,n,n+1)\right) $, $ \gamma_p:=h_p\left(n+1\right) $. Chiaramente $ \beta_p=\gamma_p $. Adesso per ogni $ 0 \le a \le b $vale $ p^{h_p(a)+1} \nmid \binom{a}{b} $,infatti contanteggiando i primi con DePolignac vediamo che ognuno degli $ h_p(a) $ addendi è non negativo e minore di $ 2 $(*). Per ogni $ 0 \le j \le n $ definiamo $ \displaystyle a_j:=(n+1)\binom{n}{j}=(n-j+1)\binom{n+1}{j}=(j+1)\binom{n+1}{j+1} $. Dato che per la (*) vale $ \max\{h_p\binom{n}{j},h_p\binom{n+1}{j},h_p\binom{n+1}{j+1}\} \le \gamma_p $, abbiamo $ p^{\gamma_p+1} \mid a_j $ solo se $ p \mid \text{gcd}(n+1,n-j+1,j+1) $, ma allora $ p \mid (n+1)-(n-j+1)-(j+1)=-1 $, che è assurdo. Dall'altra parte, $ \upsilon_p(a_{p^{\gamma_p}-1})=\gamma_p $. Ciò mostra che $ \alpha_p=\beta_p=\gamma_p $. []
The only goal of science is the honor of the human spirit.

Rispondi