Leggendo un altro topic mi è venuta in mente questa cosa. Orsù, dimostrarela!
Fissato un primo $p$ e due interi $m>n$, siano $m=kp+a$ e $n=hp+b$ le usuali divisioni euclidee con resto, allora si ha
$${m\choose n}\equiv {k\choose h}{a\choose b}\quad\bmod p\;.$$
Divisione con resto per i binomiali
Re: Divisione con resto per i binomiali
$\displaystyle a! = 1\cdot 2 \dots \cdot a \equiv (1+pk)(2+pk)\dots (a+pk) \equiv \binom{a+pk}{a}a! \pmod{p}$ e quindi
$\displaystyle\binom{a+pk}{a} \equiv 1 \Rightarrow 1 \equiv\binom{a+pk}{a}\binom{b+ph}{b} \equiv \binom{a+pk}{b+ph}\cdot \frac{b!(ph)!}{a!(pk)!}[a-b +p(k-h)]! \equiv 1 $
da cui $\displaystyle \binom{m}{n} \equiv \frac{a!(pk)!}{b!(ph)![a-b +p(k-h)]!}$
Ma siccome dal fatto che $\displaystyle\binom{a+pk}{a} \equiv 1$ deriva che $(pk+a)! \equiv a!(pk)!$, l'equzione sopra diventa
$$\displaystyle \binom{m}{n} \equiv \frac{a!(pk)!}{b!(ph)!(a-b)![p(k-h)]!} \equiv \binom{a}{b}\binom{pk}{ph} \pmod{p}$$
Resta da dimostrare quindi che $\binom{pk}{ph} \equiv \binom{k}{h} \pmod{p}$. Si consideri ora una matrice$A$, $p\times k$ ( $p$ colonne e $k$ righe) tale che $a_{rc} = r\cdot c$ e il cui elemento più in alto a sinistra è $a_{pk}$. è chiaro che il prodotto di tutti gli elementi della matrice è pari a $(pk)!$. Svolgendo ora il prodotto della $i$ esima riga dall'alto si ha che questo è pari a $p!(k-i)^p$ e che quindi il prodotto di tutti gli elementi della matrice è $(pk)! = p!^kk!^p$. Si ha quindi che
$$\displaystyle \binom{pk}{ph} \equiv \frac{p!^kk!^p}{p!^hh!^pp!^{k-h}(k-h)!^p} \equiv \binom{k}{h}^p \equiv \binom{k}{h} \pmod{p} $$
che per quanto detto prima implica la tesi
$\displaystyle\binom{a+pk}{a} \equiv 1 \Rightarrow 1 \equiv\binom{a+pk}{a}\binom{b+ph}{b} \equiv \binom{a+pk}{b+ph}\cdot \frac{b!(ph)!}{a!(pk)!}[a-b +p(k-h)]! \equiv 1 $
da cui $\displaystyle \binom{m}{n} \equiv \frac{a!(pk)!}{b!(ph)![a-b +p(k-h)]!}$
Ma siccome dal fatto che $\displaystyle\binom{a+pk}{a} \equiv 1$ deriva che $(pk+a)! \equiv a!(pk)!$, l'equzione sopra diventa
$$\displaystyle \binom{m}{n} \equiv \frac{a!(pk)!}{b!(ph)!(a-b)![p(k-h)]!} \equiv \binom{a}{b}\binom{pk}{ph} \pmod{p}$$
Resta da dimostrare quindi che $\binom{pk}{ph} \equiv \binom{k}{h} \pmod{p}$. Si consideri ora una matrice$A$, $p\times k$ ( $p$ colonne e $k$ righe) tale che $a_{rc} = r\cdot c$ e il cui elemento più in alto a sinistra è $a_{pk}$. è chiaro che il prodotto di tutti gli elementi della matrice è pari a $(pk)!$. Svolgendo ora il prodotto della $i$ esima riga dall'alto si ha che questo è pari a $p!(k-i)^p$ e che quindi il prodotto di tutti gli elementi della matrice è $(pk)! = p!^kk!^p$. Si ha quindi che
$$\displaystyle \binom{pk}{ph} \equiv \frac{p!^kk!^p}{p!^hh!^pp!^{k-h}(k-h)!^p} \equiv \binom{k}{h}^p \equiv \binom{k}{h} \pmod{p} $$
che per quanto detto prima implica la tesi
"Se [...] non avessi amore, non sarei nulla."
1Cor 13:2
"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102
1Cor 13:2
"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102
Re: Divisione con resto per i binomiali
Uhm ... intanto l'inizio non mi sembra chiaro si applichi anche al caso $a<b$, che comunque può capitare.
Poi, $6!=720$, $6=2\cdot3$ ma $(2!)^3(3!)^2=8\cdot36=288$, quindi ammetto di non aver capito l'ultimo paragrafo.
Poi, $6!=720$, $6=2\cdot3$ ma $(2!)^3(3!)^2=8\cdot36=288$, quindi ammetto di non aver capito l'ultimo paragrafo.
Re: Divisione con resto per i binomiali
devo aver cannato i conti "Se [...] non avessi amore, non sarei nulla."
1Cor 13:2
"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102
1Cor 13:2
"[...] e se io non so pentirmi del passato, la libertà è un sogno"
Soren Kierkegaard, Aut-Aut, Ed. Mondadori, pag. 102
Re: Divisione con resto per i binomiali
editato il tex . EG
------------------
Faccio innanzitutto il caso $a<b$. In tal caso $\displaystyle\binom{a}{b} \equiv \displaystyle\binom{a+p}{b} \pmod p$. Ma si ha $\displaystyle\binom{a+p}{b}=\dfrac{(a+p)!}{b!(p+a-b)!}$ e contando i fattori $p$ ne abbiamo sicuramente esattamente uno al numeratore, perché $p \leq a+p < 2p$ ed esattamente zero al denominatore perché $0 \leq b < p$ e $0 < p+a-b < p$ essendo $a-b<0$. Dunque $p|\displaystyle\binom{a+p}{b}$ ma per la congruenza iniziale si ha anche
$\displaystyle\binom{a}{b} \equiv 0 \pmod p$. Allora non resta che mostrare che $\displaystyle\binom{kp+a}{hp+b} \equiv 0 \pmod p$. Questo è vero perché
$$\displaystyle\binom{kp+a}{hp+b} = \dfrac{(kp+a)!}{(hp+b)![(k-h)p+a-b]!}$$
dove $v_p((kp+a)!)=k+v_p(k!)$ e
$$v_p((hp+b)![(k-h)p+a-b]!) = v_p ((hp+b)!)+ v_p([k-h]p+a-b]!) = h+v_p(h!) + k-h-1 +v_p(k-h-1)!=$$
$$ = k - 1 + v_p(h!(k-h-1)!)$$
perché $a-b<0$ e "non si raggiunge" $(k-h)p$. Ora basta mostrare che $v_p(k!) \geq v_p(h!(k-h-1)!)$. Ma sicuramente è vero perché $v_p(k!) \geq v_p(h!(k-h)!) \geq v_p(h!(k-h-1)!)$.
Suppongo ora $a \geq b$. Dimostro innanzitutto che $\displaystyle\binom{kp}{hp}\equiv\displaystyle\binom{k}{h} \pmod p$. Si ha, infatti, che $$\displaystyle\binom{kp}{hp} = \dfrac{(kp)!}{(hp)![(k-h)p]!} = \dfrac{\displaystyle\prod_{i=0}^{k-1}\left(\displaystyle\prod_{j=1}^{p-1} ip+j\right)\cdot k!p^k}{\displaystyle\prod_{i=0}^{h-1}\left(\displaystyle\prod_{j=1}^{p-1} ip+j\right)\cdot h!p^h \cdot \displaystyle\prod_{i=0}^{k-h-1}\left(\displaystyle\prod_{j=1}^{p-1} ip+j\right)\cdot (k-h)!p^{k-h}}\;.$$
Isolando l'altro binomiale, semplificando e moltiplicando si ottiene
$$\displaystyle\binom{kp}{hp} \cdot \displaystyle\prod_{i=0}^{h-1}\left(\displaystyle\prod_{j=1}^{p-1} ip+j\right) \cdot \displaystyle\prod_{i=0}^{k-h-1}\left(\displaystyle\prod_{j=1}^{p-1} ip+j\right) = \displaystyle\binom{k}{h} \cdot \displaystyle\prod_{i=0}^{k-1}\left(\displaystyle\prod_{j=1}^{p-1} ip+j\right)\;.$$
Ora guardando tutto modulo $p$, si ottiene che $\displaystyle\binom{kp}{hp} \cdot (p-1)!^k \equiv \displaystyle\binom{k}{h} \cdot (p-1)!^k$, da cui dividendo per $(p-1)!^k$, che è invertibile, si ha la tesi.
Ora si ha
$$\displaystyle\binom{kp+a}{hp+b}= \dfrac{(kp)!\displaystyle\prod_{i=1}^a (kp+i)}{(hp)!\displaystyle\prod_{i=1}^b (hp+i) \cdot [(k-h)p!]\displaystyle\prod_{i=1}^{a-b}[(k-h)p+i]}\;.$$
Da ciò si ha
$$\displaystyle\binom{kp+a}{hp+b} \cdot \displaystyle\prod_{i=1}^b (hp+i) \cdot \displaystyle\prod_{i=1}^{a-b}[(k-h)p+i] = \displaystyle\binom{kp}{hp} \cdot \displaystyle\prod_{i=1}^a (kp+i)\;.$$
Guardando modulo $p$ si ha $\displaystyle\binom{kp+a}{hp+b} \cdot b!(a-b)! \equiv \displaystyle\binom{kp}{hp} \cdot a! \pmod p$, da cui dividendo per $b!(a-b)!$ sicuramente invertibile poiché $b<p$, così come $a-b<p$, si ha $\displaystyle\binom{kp+a}{hp+b} \equiv \displaystyle\binom{k}{h}\displaystyle\binom{a}{b} \pmod p$ dove ho utilizzato anche il risultato precedente. (Posso suppore $a \neq 0$, altrimenti essendo $a\geq b$ mi riconduco al caso precedente. Però se $b=0$ o $a=b$ gli estremi di alcune produttorie in quest'ultima parte diventano $0$: per sistemare questo problema basta assumere che in tal caso tali sommatorie non ci siano).
Spero sia tutto corretto
------------------
Faccio innanzitutto il caso $a<b$. In tal caso $\displaystyle\binom{a}{b} \equiv \displaystyle\binom{a+p}{b} \pmod p$. Ma si ha $\displaystyle\binom{a+p}{b}=\dfrac{(a+p)!}{b!(p+a-b)!}$ e contando i fattori $p$ ne abbiamo sicuramente esattamente uno al numeratore, perché $p \leq a+p < 2p$ ed esattamente zero al denominatore perché $0 \leq b < p$ e $0 < p+a-b < p$ essendo $a-b<0$. Dunque $p|\displaystyle\binom{a+p}{b}$ ma per la congruenza iniziale si ha anche
$\displaystyle\binom{a}{b} \equiv 0 \pmod p$. Allora non resta che mostrare che $\displaystyle\binom{kp+a}{hp+b} \equiv 0 \pmod p$. Questo è vero perché
$$\displaystyle\binom{kp+a}{hp+b} = \dfrac{(kp+a)!}{(hp+b)![(k-h)p+a-b]!}$$
dove $v_p((kp+a)!)=k+v_p(k!)$ e
$$v_p((hp+b)![(k-h)p+a-b]!) = v_p ((hp+b)!)+ v_p([k-h]p+a-b]!) = h+v_p(h!) + k-h-1 +v_p(k-h-1)!=$$
$$ = k - 1 + v_p(h!(k-h-1)!)$$
perché $a-b<0$ e "non si raggiunge" $(k-h)p$. Ora basta mostrare che $v_p(k!) \geq v_p(h!(k-h-1)!)$. Ma sicuramente è vero perché $v_p(k!) \geq v_p(h!(k-h)!) \geq v_p(h!(k-h-1)!)$.
Suppongo ora $a \geq b$. Dimostro innanzitutto che $\displaystyle\binom{kp}{hp}\equiv\displaystyle\binom{k}{h} \pmod p$. Si ha, infatti, che $$\displaystyle\binom{kp}{hp} = \dfrac{(kp)!}{(hp)![(k-h)p]!} = \dfrac{\displaystyle\prod_{i=0}^{k-1}\left(\displaystyle\prod_{j=1}^{p-1} ip+j\right)\cdot k!p^k}{\displaystyle\prod_{i=0}^{h-1}\left(\displaystyle\prod_{j=1}^{p-1} ip+j\right)\cdot h!p^h \cdot \displaystyle\prod_{i=0}^{k-h-1}\left(\displaystyle\prod_{j=1}^{p-1} ip+j\right)\cdot (k-h)!p^{k-h}}\;.$$
Isolando l'altro binomiale, semplificando e moltiplicando si ottiene
$$\displaystyle\binom{kp}{hp} \cdot \displaystyle\prod_{i=0}^{h-1}\left(\displaystyle\prod_{j=1}^{p-1} ip+j\right) \cdot \displaystyle\prod_{i=0}^{k-h-1}\left(\displaystyle\prod_{j=1}^{p-1} ip+j\right) = \displaystyle\binom{k}{h} \cdot \displaystyle\prod_{i=0}^{k-1}\left(\displaystyle\prod_{j=1}^{p-1} ip+j\right)\;.$$
Ora guardando tutto modulo $p$, si ottiene che $\displaystyle\binom{kp}{hp} \cdot (p-1)!^k \equiv \displaystyle\binom{k}{h} \cdot (p-1)!^k$, da cui dividendo per $(p-1)!^k$, che è invertibile, si ha la tesi.
Ora si ha
$$\displaystyle\binom{kp+a}{hp+b}= \dfrac{(kp)!\displaystyle\prod_{i=1}^a (kp+i)}{(hp)!\displaystyle\prod_{i=1}^b (hp+i) \cdot [(k-h)p!]\displaystyle\prod_{i=1}^{a-b}[(k-h)p+i]}\;.$$
Da ciò si ha
$$\displaystyle\binom{kp+a}{hp+b} \cdot \displaystyle\prod_{i=1}^b (hp+i) \cdot \displaystyle\prod_{i=1}^{a-b}[(k-h)p+i] = \displaystyle\binom{kp}{hp} \cdot \displaystyle\prod_{i=1}^a (kp+i)\;.$$
Guardando modulo $p$ si ha $\displaystyle\binom{kp+a}{hp+b} \cdot b!(a-b)! \equiv \displaystyle\binom{kp}{hp} \cdot a! \pmod p$, da cui dividendo per $b!(a-b)!$ sicuramente invertibile poiché $b<p$, così come $a-b<p$, si ha $\displaystyle\binom{kp+a}{hp+b} \equiv \displaystyle\binom{k}{h}\displaystyle\binom{a}{b} \pmod p$ dove ho utilizzato anche il risultato precedente. (Posso suppore $a \neq 0$, altrimenti essendo $a\geq b$ mi riconduco al caso precedente. Però se $b=0$ o $a=b$ gli estremi di alcune produttorie in quest'ultima parte diventano $0$: per sistemare questo problema basta assumere che in tal caso tali sommatorie non ci siano).
Spero sia tutto corretto
"Il bon ton è la grazia del saper vivere, la leggerezza dell' esistere." (Lina Sotis, perfidamente elegante)
Re: Divisione con resto per i binomiali
Fidandomi dei conti con le valutazioni (su cui mi incarto regolarmente), mi sembra tornare.
Se qualcuno vuole, c'è un'altra soluzione che passa per questo hint:
Se qualcuno vuole, c'è un'altra soluzione che passa per questo hint:
Testo nascosto:
Re: Divisione con resto per i binomiali
Boh, io la scrivo ...
$$p(x)=(1+x)^m-(1+x)^a(1+x^p)^k=(1+x)^{a+kp}-(1+x)^a(1+x^p)^k=(1+x)^a((1+x)^{kp}-(1+x^p)^k)=$$
$$=(1+x)^a((1+x)^p-1-x^p)(\textrm{roba})$$
e $(1+x)^p-1-x^p$ ha tutti i coefficienti multipli di $p$, quindi anche $p(x)$.
Ora basta notare che il coefficiente di $x^n$ in $(1+x)^m$ è $m \choose n$, mentre in $(1+x)^a(1+x^p)^k$ deve essere il prodotto tra i coefficienti di $x^b$ e $x^{hp}$ nei due fattori (infatti tutti gli esponenti dello sviluppo del primo fattore sono $\leq a<p$), quindi è ${a\choose b}{k\choose h}$ (e se $b>a$ allora $x^b$ non compare e quindi non compare $x^n$ dopo la moltiplicazione, quindi questo contributo è $0$).
Dunque $p$ divide ${m\choose n}-{a\choose b}{k\choose h}$.
$$p(x)=(1+x)^m-(1+x)^a(1+x^p)^k=(1+x)^{a+kp}-(1+x)^a(1+x^p)^k=(1+x)^a((1+x)^{kp}-(1+x^p)^k)=$$
$$=(1+x)^a((1+x)^p-1-x^p)(\textrm{roba})$$
e $(1+x)^p-1-x^p$ ha tutti i coefficienti multipli di $p$, quindi anche $p(x)$.
Ora basta notare che il coefficiente di $x^n$ in $(1+x)^m$ è $m \choose n$, mentre in $(1+x)^a(1+x^p)^k$ deve essere il prodotto tra i coefficienti di $x^b$ e $x^{hp}$ nei due fattori (infatti tutti gli esponenti dello sviluppo del primo fattore sono $\leq a<p$), quindi è ${a\choose b}{k\choose h}$ (e se $b>a$ allora $x^b$ non compare e quindi non compare $x^n$ dopo la moltiplicazione, quindi questo contributo è $0$).
Dunque $p$ divide ${m\choose n}-{a\choose b}{k\choose h}$.