Congruenza coefficiente binomiale
Ciao, amici! Stavolta volevo chiedere una cosina che probabilmente sarà semplice semplice per gli altri utenti del forum, ma io non arrivo alla conclusione: se il numero $p\in\mathbb{N}$ primo è tale che \(p\nmid m\), risulta da quanto leggo* che \[\frac{1}{m}\binom{mp^k}{p^k}\equiv 1\text{ mod }(p)\]È chiaro che il membro sinistro è un intero positivo uguale a \(\binom{mp^k-1}{p^k-1}\). Ora, se $mteorema di Lucas, che ho avuto la felicità di scoprire in rete cercando disperatamente una risposta a questa questione, ma se $m>p$ non mi spiego come si derivi questa congruenza...
Qualcuno ne sa di più?
\(\infty\) grazie a tutti!!!
*Si tratta del numero mod \((p)\) dei $p$-sottogruppi di Sylow di un gruppo, ma direi che la congruenza sia un problema di combinatoria e di aritmetica modulare. Mi scuso con i moderatori se ho sbagliato sezione, ma dato l'utilizzo di quest'ultima mi sembrava meglio postare qui che in Statistica...
Qualcuno ne sa di più?
\(\infty\) grazie a tutti!!!
*Si tratta del numero mod \((p)\) dei $p$-sottogruppi di Sylow di un gruppo, ma direi che la congruenza sia un problema di combinatoria e di aritmetica modulare. Mi scuso con i moderatori se ho sbagliato sezione, ma dato l'utilizzo di quest'ultima mi sembrava meglio postare qui che in Statistica...
Risposte
Secondo me, se la scrivi così:
\[
\binom{mp^k}{p^k}\equiv m\,\text{mod}(p)
\]
e provi a dimostrarla via definizione e calcoli: concludi!
\[
\binom{mp^k}{p^k}\equiv m\,\text{mod}(p)
\]
e provi a dimostrarla via definizione e calcoli: concludi!
Con un calcolo diretto ci avevo provato per prima cosa, ma non mi è riuscito per la mia scarsa dimestichezza con questo genere di cose (ho sempre più voglia di comprarmi un libro di combinatoria)...
Mi sembrerebbe che, usando l'uguaglianza \(X^{p^r}+1=(X+1)^{p^r}\) in \(\mathbb{F}_p[X]\), analogamente a quanto ho trovato fatto per il teorema di Lucas, si possa scrivere\[\sum_{i=0}^{mp^k}\binom{mp^k}{i}X^i =(1+X)^{mp^k}\equiv(1+X^{p^k})^m=\sum_{i=0}^{m}\binom{m}{i}X^{ip^k}\text{ mod }(p)\]e mi parrebbe immediato constatare che i coefficienti di \(X^{p^k}\) diano la congruenza cercata.
\(\infty\) grazie ancora!!!
Mi sembrerebbe che, usando l'uguaglianza \(X^{p^r}+1=(X+1)^{p^r}\) in \(\mathbb{F}_p[X]\), analogamente a quanto ho trovato fatto per il teorema di Lucas, si possa scrivere\[\sum_{i=0}^{mp^k}\binom{mp^k}{i}X^i =(1+X)^{mp^k}\equiv(1+X^{p^k})^m=\sum_{i=0}^{m}\binom{m}{i}X^{ip^k}\text{ mod }(p)\]e mi parrebbe immediato constatare che i coefficienti di \(X^{p^k}\) diano la congruenza cercata.
\(\infty\) grazie ancora!!!
"DavideGenova":Come?
...e mi parrebbe immediato constatare che i coefficienti di \(X^{p^k}\) diano la congruenza cercata...
Sto delirando? A sinistra vedo che l'indeterminata $X^i$ di esponente $i=p^k$ ha coefficiente \(\binom{mp^k}{p^k}\), mentre nella sommatoria a destra direi proprio (a meno che non sappia neanche più di operazioni aritmetiche) che l'indeterminata di uguale esponente è $X^{ip^k}$ con $i=1$, che ha coefficiente \(\binom{m}{1}=m\)... Da questo mi sarebbe sembrato di ottenere la congruenza da te indicata, da cui dedurrei che, se esiste un $k'\in\mathbb{Z}$ tale che \(\binom{mp^k}{p^k}=m+k'p\), dato che \(m|\binom{mp^k}{p^k}\) e \(m|m\), $m$ deve dividere anche $k'p$, perciò \(\frac{1}{m}\binom{mp^k}{p^k}\equiv 1\text{ mod }(p)\).
Chissà quante scemenze sto dicendo...
$\infty$ grazie per la risposta!
Chissà quante scemenze sto dicendo...
$\infty$ grazie per la risposta!
"DavideGenova":Nulla da eccepire; ma non capisco perché quei due polinomi devono avere coefficienti equivalenti grado per grado?! Forse perché si ragiona in modulo primo?
Sto delirando? A sinistra vedo che l'indeterminata $ X^i $ di esponente $ i=p^k $ ha coefficiente \( \binom{mp^k}{p^k} \), mentre nella sommatoria a destra direi proprio (a meno che non sappia neanche più di operazioni aritmetiche) che l'indeterminata di uguale esponente è $ X^{ip^k} $ con $ i=1 $, che ha coefficiente \( \binom{m}{1}=m \)...
Due polinomi uguali sono convinto (ma le mie convinzioni possono benissimo essere fallaci) che abbiano necessariamente coefficienti uguali, per definizione, quindi, se \(\sum_{i=0}^{mp^k}\binom{mp^k}{i}X^i =\sum_{i=0}^{m}\binom{m}{i}X^{ip^k}\in\mathbb{Z}/p\mathbb{Z}[X]\)...
Sbaglio?
Sbaglio?
Su campi finiti puoi avere polinomi distinti che producono la stessa funzione polinomiale; ad esempio il polinomio \(\displaystyle1\) e il polinomio \(\displaystyle x^2+x+1\) determinano entrambi la funzione polinomiale costante a \(\displaystyle1\) su \(\displaystyle\mathbb{Z}_2\)!
Non possono però esistere per definizione polinomi uguali (non solo tali che un omomorfismo di valutazione assuma lo stesso valore) in \(\mathbb{Z}/p\mathbb{Z}\) con diversi coefficienti per la stessa incognita, giusto? Se è così (e spero proprio che sia veramente così, altrimenti significa che non capito nulla di nulla di che cos'è un polinomio 
) e \( X^{p^r}+1=(X+1)^{p^r} \in\mathbb{Z}/p\mathbb{Z}[X] \) mi sembrerebbe chiaro che i coefficienti di $X^{p^k}$ debbano essere gli stessi elementi di \(\mathbb{Z}/p\mathbb{Z}\) nei due polinomi e quindi numeri interi congruenti mod ($p$)...
) e \( X^{p^r}+1=(X+1)^{p^r} \in\mathbb{Z}/p\mathbb{Z}[X] \) mi sembrerebbe chiaro che i coefficienti di $X^{p^k}$ debbano essere gli stessi elementi di \(\mathbb{Z}/p\mathbb{Z}\) nei due polinomi e quindi numeri interi congruenti mod ($p$)...
Confermo DavideGenova, la tua dimostrazione è esatta.
Fiuh, quello che mi dici mi rincuora.
\(\infty\) grazie anche a te, Martino!!!
\(\infty\) grazie anche a te, Martino!!!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo