Calcul des coefficients binomiaux modulo p — Les-mathematiques.net The most powerful custom community solution in the world

Calcul des coefficients binomiaux modulo p

Bonjour,

Des choses nouvelles que je n'avais jamais vues de ma vie. Je bloque sur un petit détail de la preuve, le passage encadré en rouge.
Je ne connaissais pas cette technique avec les divisions en cascade par $b$ pour trouver l'écriture en base $b$.




Réponses

  • C'est une convention pour que la formule soit vraie. Tu connaissais d'autres techniques pour trouver l'écriture en base quelconque ? Parce-que c'est plutôt celle-ci qu'on apprend en premier en général...
  • Je ne connaissais pas la technique.

    Je n'ai pas compris de quelle convention il s'agit pour montrer que le coefficient devant $X^m$ est nul si il existe un entier $i$ tel que $n_i < m_i$.
    J'ai l'impression que la convention c'est pour la suite de la phrase.
  • Modifié (4 Aug)
    Oups ! Tu as raison, j'ai lu trop vite. En fait, c'est parce-que le coefficient devant $X^k$ d'un polynôme de degré $n$ est nul si $k > n$.
  • Modifié (4 Aug)
    Prends plein d'allumettes. 
    Plein, quelques centaines ou quelques milliers.
    Et maintenant, on va les compter.  En base dix pour se raccrocher à des choses connues.
    Tu vas regrouper les allumettes en paquets de 10 (on va appeler ça des dizaines).
    On va ensuite regrouper ces dizaines en paquets de 10, et on va appeler ça des centaines.
    On va ensuite regrouper ces centaines en paquets de 10 et on va appeler ça des milliers.
    A chaque fois, sauf coup de chance, il reste des paquets 'orphelins'.
    Quand je constitue mes dizaines, s'il reste 3 allumettes seules (3 unités), je vais noter 3.
    Quand je regroupe mes dizaines pour constituer les centaines, s'il reste 2 dizaines, je vais écrire un 2 devant le 3.
    etc etc.
    J'ai la certitude à chaque fois que le reste est un nombre entre 0 et 9

    A chaque étape, on fait des groupes de dix, (c.a.d des divisions par dix) et on regarde le reste.  Si au lieu de faire des groupes de dix, on fait des groupes de huit, on aura l'écriture en base 8.

    J'écris dix en lettres et pas en chiffres , et c'est volontaire.

    En base dix, on a des mots comme dizaines, centaines, milliers, et on le fait depuis qu'on est petit. C'est facile. En base autre, on n'a pas ces mots, et on le fait très rarement. Mais ce n'est pas plus difficile dans l'absolu.
    En base seize par exemple, on prendra soin d'écrire les CHIFFRES entre dix et quinze avec un symbole, comme les lettres A,B,C,D,E,F, et surtout ne pas les écrire 10, 11, 12, 13, 14, 15 !
  • En fait, @Oshine, tu peux supprimer la dernière phrase de cette démo : elle ne sert qu'à rassurer les vacuophobes.
    La démonstration est déjà finie à l'égalité précédente.

    Par contre, je suis fort étonné que tu comprennes cette démonstration... qui n'est en fait que du dénombrement... alors que je croyais que tu avais du mal avec le dénombrement.
  • Bibix a dit :
    Oups ! Tu as raison, j'ai lu trop vite. En fait, c'est parce-que le coefficient devant $X^k$ d'un polynôme de degré $n$ est nul si $k > n$.
    Oui mais je ne comprends toujours pas le lien direct avec le $n_i < m_i$.

    @bisam du dénombrement caché c'est de l'identification des coefficients et unicité d'un polynôme.

    Pas compris pourquoi la dernière phrase est inutile.

  • Si tu n'as pas compris cela, alors c'est sûr que tu n'as pas compris la démonstration. Le point important est que $k_i = m_i$ !
  • @lourrran: tu m'as précédé, je voulais écrire un truc du même genre. Par contre, il y a je crois, une notation de++ courante en base b>dix; prenons par exemple la base seize, on va mixer les notations. Ainsi, $(15:13)_{seize}$ représente $15 \times 16^1+13 \times 16^0$ ; plus besoin alors des lettres A, B, C, D, ... :wink:
  • Tu même pas trouvé l'équivalent de ${n!e}$, et comme tu ne trouves pas tu postes autre chose... Que tu ne trouveras pas. Tu as une idée pour trouver 3,75 en base 7?
  • Modifié (4 Aug)
    Pourquoi tu parles de décimaux non entiers alors qu'on est en arithmétique ?
    Le livre donne plusieurs exemples par la suite.
  • Modifié (5 Aug)
    @Bibix ok merci le $k_i=m_i$ provient de l'unicité de l'écriture en base $b$.
    J'ai compris la démo, de la à la refaire seul, c'est un peu un niveau élevé pour moi.
    Par exemple calculer $\binom{9}{19} \equiv [3]$.
    On doit écrire $9$ et $19$ en base $3$.
    On a $9= 3 \times 3 + 0$ donc $a_0=0$
    $3= 3 \times 1 + 0$ donc $a_1=0$
    $1=3 \times 0+1$ donc $a_2=1$
    $\boxed{9=0+ 0 \times 3 + 0 \times 3^2}$
    De même $9=0+0 \times 3 + 1 \times 3^2$.
    Donc $\binom{9}{19}  \equiv \binom{1}{0} \times \binom{0}{0} \times \binom{2}{1} \equiv 2 [3]$.
  • Modifié (5 Aug)
    Je traduis ce que tu as écris : 
    Par exemple, calculer $0 = C_9^{19}$ modulo $3$, on utilise la méthode pour trouver $9 = 0$. De même, $9 = 3^2$. Donc $0 \equiv 2 [3]$. Bon j'ai compris que ce n'était que des coquilles mais concentre toi un peu, parce-que c'est difficile à lire.
    Si tu as compris la démo, alors tu devrais être capable de la refaire tout seul et d'en déduire des exercices, etc... . Ce n'est pas grave que tu ne l'aie pas comprise, mais tu devrais au moins être capable de le reconnaitre. À moins que pour toi, comprendre une démo se résume à comprendre comment utiliser le résultat, mais dans ce cas, je ne peux plus rien pour toi...
  • Pour compléter ce que dit @lourrran je propose cette vidéo https://www.youtube.com/watch?v=lP9PaDs2xgQ
  • Ou autre manière de voir les choses, l'algorithme de Hölder pour évaluer les polynômes : 

    $a_{0} + a_{1}X + ... + a_{n}X^{n} = a_{0} + X(a_{1} + X(a_{2} + X(...(a_{n-1} + Xa_{n}))))$

    Donc la première division donne le premier coefficient (regarde "modulo X"), la division de la première parenthèse le second, etc.

    Ou plus concrètement, si tu as le nombre 512, pour avoir le chiffre des unités tu regardes modulo 10, pour avoir le second tu arrondis à 510 et simplifies par 10 pour obtenir 51, puis tu regardes modulo 10 pour avoir le 1, et de la même manière tu obtiens le 5.
  • Modifié (5 Aug)
    Si on définit pour n'importe quels entiers naturels $n$ et $p$ le nombre $\binom{n}{p}$ comme étant égal au nombre de façons de choisir $p$ objets parmi $n$ alors il n'est pas nécessaire de définir une "convention" pour le cas où $n$ est strictement plus petit que $p$.
    Avec cette vision, la distinction entre les cas $\forall i\in\{1,\dots,r\}, m_i \leq n_i$ d'une part et son contraire $\exists i \in\{1,\dots,r\},m_i>n_i$ d'autre part est complètement inutile.
    Le point important est celui qui n'est pas écrit mathématiquement, mais uniquement écrit en français : "les entiers $k_i$ doivent être les chiffres de $m$ en base $p$", autrement dit : $\forall i\in\{1,\dots,r\}, k_i=m_i$.
    Quant à ton calcul de $\binom{9}{19}$, il est hallucinant !! Il y a des erreurs partout ! (et en fait, j'imagine que tu voulais calculer plutôt $\binom{19}{9}$)
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!