mcm e binomiali

[Simo_the_wolf]

Dimostrare che il mcm tra $ \displaystyle 1,2,3,...,n $ e il mcm tra $ \displaystyle \binom n1, \binom n2, .... , \binom nn $ sono uguali se e solo se $ n+1 $ è un numero primo

[Simo_the_wolf]

UP!! dài, impegnatevi un poco di più...

[frengo]

Dimostrare che il mcm tra $ \displaystyle 1,2,3,...,n $ e il mcm tra $ \displaystyle \binom n1, \binom n2, .... , \binom nn $ sono uguali se e solo se $ n+1 $ è un numero primo

1)se n+1 non è un numero primo, allora i due m.c.m. non sono uguali.

sia p un numero primo che divide n+1,e x la massima potenza tale che $ p^x<n $, e quindi anche la massima potenza di p che divide l'm.c.m. dei numeri tra 1 e n.

ora consideriamo un qualsiasi coefficiente binomiale:
$ \displaystyle \frac{n(n-1)...(n-k+2)(n-k+1)}{k(k-1)...3\cdot2\cdot1} $

notiamo che c'è una corrispondenza tra i resti mod p dei fattori, presi in ordine inverso:
$ (n)+(1)\equiv0 (mod p) $
$ (n-1)+(2)\equiv0 (mod p) $
$ (n-k+2)+(k-1)\equiv0 (mod p) $
$ (n-k+1)+(k)\equiv0 (mod p) $
(ho usato le parentesi per far capire bene quali sono i fattori)

Da questo fatto deriva il fatto che nel numeratore e nel denominatore ci sono lo stesso numero di multipli di p.

Tra tutti questi alcuni sono multipli anche di p^2, e si vede facilmente che il numeratore può al massimo averne uno in più, quindi il numeratore può al massimo "guadagnare" un fattore p rispeto al denominatore.

Ragionando allo stesso modo per le altre potenze di p fino alla x definita all'inizio, si vede che alla fine il numeratore può guadagnare dal denominatore al massimo x-1 fattori p, cioè
$ \displaystyle p^{x-1}||mcm(\binom n1, \binom n2, .... , \binom nn) $
ma visto che
$ \displaystyle p^{x}||mcm(1,2, .... ,n) $
allora
$ \displaystyle mcm(\binom n1, \binom n2, .... , \binom nn) \neq mcm(1,2,3...n) $

[Simo_the_wolf]

Bene! E metà del lavoro è fatto... Ora manca l'altra freccia, cioè se n+1 è primo allora i mcm sono uguali

[frengo]

si si per un pò mi sono dovuto "allontanare" dal computer...
la dimostrazione non è poi così diversa: se n+1 è un numero primo, per ogni primo p minore a n (e definito x come prima) dimostro che nei binomiali p appare con esponente x, e non appare con esponente maggiore di x.

i)prendiamo $ \displaystyle \binom {n}{p^x-1} $

$ \displaystyle \frac{n(n-1) ... (p^x+2)(p^x+1)(p^x)}{(n-p^x+1)(n-p^x) ... 3\cdot2\cdot1} $

la corrispondenza stavolta è così
$ (p^x+1)\equiv(1) (mod p^x) $
$ (p^x+2)\equiv(2) (mod p^x) $
$ (p^x+3)\equiv(3) (mod p^x) $
$ (n-1)\equiv(n-p^x-1) (mod p^x) $
$ (n)\equiv(n-p^x) (mod p^x) $
$ (n+1)\equiv(n-p^x+1) (mod p^x) $

per cui, visto che n+1 è primo e quindi p non divide n+1, ci sono lo stesso numero di multipli di p nei due intervalli $ (n;p^x+1) $ e $ (n-p^x+1;1) $, e visto che la congruenza è modulo p, gli esponenti di p in questi multipli sono uguali.
la massima potenza di p che divide $ \displaystyle \binom {n}{p^x-1} $ è quindi x.

ii)come prima: nel numero
$ \displaystyle \frac{n(n-1)...(n-k+2)(n-k+1)}{k(k-1)...3\cdot2\cdot1} $

il numeratore può "guadagnare" 1 fattore p sul denominatore per i multipli di $ p^1 $,uno per i multipli di $ p^2 $ e così via fino alla x-esima potenza. il massimo numero di "p" che può guadagnare è x.

come promesso(ma un pò in ritardo), la tesi è dimostrata

ciao ciao

[HiTLeuLeR]

Uh... Per ogni n \in \mathbb{N}: \lcm(1, 2, \ldots, n+1) = (n+1) \cdot \lcm\!\left(\binom{n}{1}, \binom{n}{2}, \ldots, \binom{n}{n}\right).