Forum de mathématiques - Bibm@th.net

Jippy13011

Membre

Inscription : 16-09-2023

Messages : 21

Preuve de $\binom{pa}{pb}\equiv \binom{a}{b} \left [ p \right ] $

Bonjour

Je cherche à démontrer la formule suivante pour tout nombre a,b, p avec p premier.

$
\binom{pa}{pb}\equiv \binom{a}{b}  \left [ p \right ]
$

Merci pour l'attention que vous porterez à ce message.

PS: j'ai consulté le web mais certaines démos ne sont pas expliquée dans le détail (à mon avis).

Dernière modification par Jippy13011 (16-09-2023 13:37:27)

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 464

Re : Preuve de $\binom{pa}{pb}\equiv \binom{a}{b} \left [ p \right ] $

Bonjour,
Faut-il lire l'égalité comme une congruence ?
Qui est [tex]m[/tex] ?

Dernière modification par Michel Coste (16-09-2023 13:15:50)

Jippy13011

Membre

Inscription : 16-09-2023

Messages : 21

Re : Preuve de $\binom{pa}{pb}\equiv \binom{a}{b} \left [ p \right ] $

Oui désolé, je suis allez trop vite. m et p sont identique. J'ai rectifié dans le post initial.

Dernière modification par Jippy13011 (16-09-2023 13:28:16)

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 464

Re : Preuve de $\binom{pa}{pb}\equiv \binom{a}{b} \left [ p \right ] $

On peut raisonner sur [tex]\mathbb Z/p\mathbb Z[/tex].
Calculons [tex](1+X)^{ap}[/tex] dans [tex](\mathbb Z/p\mathbb Z)[X][/tex].
D'un côté c'est [tex](1+X)^{ap}= \sum_{k=0}^{ap} \binom{ap}{k} X^k[/tex] (tous les coefficients biniomiaux sont à prendre modulo [tex]p[/tex], bien sûr).
De l'autre c'est [tex]((1+X)^p)^a=(1+X^p)^a= \sum_{\ell=0}^a \binom{a}{\ell}X^{\ell p}[/tex] (on sait que les coefficients binomiaux [tex]\binom{p}{m}[/tex] sont divisibles par [tex]p[/tex] pour [tex]0<m<p[/tex]).
Il suffit d'identifier les coefficients de [tex]X^{bp}[/tex].

Dernière modification par Michel Coste (16-09-2023 14:11:14)

Jippy13011

Membre

Inscription : 16-09-2023

Messages : 21

Re : Preuve de $\binom{pa}{pb}\equiv \binom{a}{b} \left [ p \right ] $

Merci Michel ! Très clair.

J'ai tendance à oublier que dans $(\mathbb{Z}/p \mathbb{Z})[X]$ les opérations sont parfois plus simples.

J'ai lu sur le site anglophone une démo probabiliste parlant de cercles concentriques mais je ne l'ai pas assimilée.

Quelqu'un pourrait il me l'expliquer ? Cette démo me parait intéressante et esthétique :).

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 464

Re : Preuve de $\binom{pa}{pb}\equiv \binom{a}{b} \left [ p \right ] $

C'est quoi, "le site anglophone" ???? Mets un lien !

Jippy13011

Membre

Inscription : 16-09-2023

Messages : 21

Re : Preuve de $\binom{pa}{pb}\equiv \binom{a}{b} \left [ p \right ] $

J'ai pas mis le lien en raison de pb technique (il me dit que c un spam).

Voici le lien "enrobé" (le filtre antispam bloque certains termes)
math puis stacque echange
questions
652886

ou bien tu tapes sur google
(pa pb) mod p

c'est le 3eme resultat

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 385

Re : Preuve de $\binom{pa}{pb}\equiv \binom{a}{b} \left [ p \right ] $

Bonjour,

https://math.sta~ckexchange.com/questions/652886/given-integers-a-ge-b-0-and-a-prime-number-p-prove-th~at-pa-choose-pb

Copier/coller dans la barre d'adresses du navigateur, supprimer le tilde ~ et valider...

      Yoshi
- Modérateur -

C'est moi qui suis responsable de la liste de mots anglais - anodins - établie il y a longtemps et qui permettait de bloquer les spams en anglais qui nous arrivait l'un après l'autre...
Ces messages étaient expédiés par des bots incapables
- de détecter l'impossibilité d'affichage
- de, sinon, savoir pourquoi et donc d'identifier les mots un par un
- de récrire lesdits messages sans ces mots (d'autant que ces spams en contenaient jusqu'à une dizaine).

Il aurait fallu, soit le faire "à la main", soit écrire un script détectant chaque mot bloquant et tenter de les contourner : mais une phrase anglaise sans ces mots n'aurait eu guère de sens ...
Alors, soit on arrive à tout bloquer, soit les mecs derrière ça se sont aperçus que ça coinçait, et ils n'avaient pas de temps à perdre avec nous...

  Donc, oui, je suis conscient du désagrément engendré, mais il est sans commune mesure avec les rafales de spams vantant des produits médicaux et paramédicaux : ils arrivaient l'un derrière l'autre d'adresses différentes : il est arrivé qu'à peine en avais-je viré une, qu'une autre arrivait...
  Vous m'en voyez navré...

@+

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 464

Re : Preuve de $\binom{pa}{pb}\equiv \binom{a}{b} \left [ p \right ] $

Merci pour le lien, la démonstration combinatoire est superbe. Je ne dirais pas que c'est une démonstration probabuiliste : en fait, elle fait intervenir une action de groupe (le groupe cyclique engendré par une rotation d'ordre p) et le décompte des orbites de cette action sur l'ensemble des choix de pb régions parmi les pa délimitées dans a couronnes concentriques  par p rayons découpant des secteurs circulaires d'angle 2*pi/p.

Jippy13011

Membre

Inscription : 16-09-2023

Messages : 21

Re : Preuve de $\binom{pa}{pb}\equiv \binom{a}{b} \left [ p \right ] $

J'ai un peu de mal à visualiser l'explication.

Michel, te serait il possible d'être plus formaliste ?

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 464

Re : Preuve de $\binom{pa}{pb}\equiv \binom{a}{b} \left [ p \right ] $

Il semble que tu as plus besoin de visulisation que de formalisation.
p=3, a=5, b=2.
Le grand disque est divisé en pa (=15) régions, on en choisit pb (=6).
Il y a [tex]\binom{pa}{pb}[/tex] configurations possibles. En voici une :

Cette configuration donne p configurations différentes par rotations d'1/p  tour.
Par contre il y a des configurations invariantes par rotation d'1/p tour, comme

Le choix d'une telle configuration est le choix de b couronnes entre cercles parmi a, où on pose les points. Il y en a [tex]\binom{a}{b}[/tex].

Dernière modification par Michel Coste (18-09-2023 09:13:55)

Jippy13011

Membre

Inscription : 16-09-2023

Messages : 21

Re : Preuve de $\binom{pa}{pb}\equiv \binom{a}{b} \left [ p \right ] $

Merci, voila qui est plus clair....mais

J'ai compris qu'il y avait 2 types de configurations...les singletons qui sont invariants par rotation (orbite à un élément) et les autres.

Ces dernières (cas de figure exposé) ont une orbite de p éléments. Mais comment en être certains ? Comment montrer qu'une rotation de k/p tour ne donne pas la même conf? et comment se sert on du fait que p est premier ? Je comprends que le groupe G des rotations 1/p est un monoïde mais est ce utile ?

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 464

Re : Preuve de $\binom{pa}{pb}\equiv \binom{a}{b} \left [ p \right ] $

Une orbite a un nombre d'éléments qui divise p.
De façon plus terre à terre : si une configuration est invariante par une rotation de k/p tour avec 0<k<p, alors comme k est premier avec p et que donc on a une identité de Bézout uk+vp=1, elle est invariante par une rotation de 1/p tour.  (répéter u fois la rotation de k/p tour).

Jippy13011

Membre

Inscription : 16-09-2023

Messages : 21

Re : Preuve de $\binom{pa}{pb}\equiv \binom{a}{b} \left [ p \right ] $

Michel, je dois avouer que j'ai du mal à voir que la rotation de 1/q et 1/r ou q,r <p d'une configuration aboutissent forcément à des résultats différents. Ce n'est pas intuitif pour moi.

Pour formaliser mon raisonnement, je considère G le groupe monoïde des rotations dans le plan de centre O et d'angle 2pi/p.

Soit une configuration x fixée (voir plus haut) qui ne soit pas pleine sur toutes les couronnes. J'appelle X, l'ensemble de toutes les configurations possibles générées par des rotation r=1/p tour de G.

Alors l'ensemble X généré par G*x est aussi une orbite et l'on a card(G) = card (Stabilisateur (x)) * card (G*x). (on utilise la relation d'equivalence gRg' si g*x=g'*x).

Or card(G) = p premier donc card(G*x)=p  ( Gx a au moins 2 éléments) et donc toute les configurations sont distincte 2 à 2 par rotation de k/p tour.

Qu'en pensez vous ? est ce bien clair ?

J'aimerais bien formaliser une démo.

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 464

Re : Preuve de $\binom{pa}{pb}\equiv \binom{a}{b} \left [ p \right ] $

J'ai dit dans mon message précédent qu'une orbite a un nombre d'éléments qui divise p. De manière générale, si G est un groupe fini qui opère sur un ensemble E, toute orbite a un cardinal qui divise l'ordre de G. La raison, comme tu l'as écrit, est que l'orbite d'un x de E est en bijection avec l'ensemble des classes à gauche pour le stabilisateur de x.

Tu fais une confusion de terminologie en parlant de "groupe monoïde". Peut-être veux-tu dire "groupe monogéne" ? En l'occurrence il s'agit ici d'un groupe cyclique (on préfère employer ce terme pour un groupe monogène fini) d'ordre p.

Je me demande si tu as bien lu le second paragraphe de mon précédent message. En tout cas, ta phrase "je dois avouer que j'ai du mal à voir que la rotation de 1/q et 1/r ou q,r <p d'une configuration aboutissent forcément à des résultats différents" ne fait aucun sens. Les rotations considérées sont des rotations d'un angle multiple de 1/p tour (des rotations du groupe cyclique engendré par la rotation de 1/p tour). Relis bien le paragraphe qui commence par "De façon plus terre à terre". Qu'est-ce que tu ne comprends pas ? Je montre que si une configuration est invariante par une rotation d'un angle multiple de 1/p tour différente de l'identité, alors elle est invariante par la rotation de 1/p tour et donc elle est une réunion de couronnes.

Dernière modification par Michel Coste (19-09-2023 10:12:35)

Jippy13011

Membre

Inscription : 16-09-2023

Messages : 21

Re : Preuve de $\binom{pa}{pb}\equiv \binom{a}{b} \left [ p \right ] $

Bonjour Michel, merci pour ton message.

Effectivement je n'ai pas utilisé le bon terme en écrivant monoide...je voulais dire engendré par un seul élément soit $\alpha$ la rotation d'angle 2pi/p..

Ensuite je me suis mal exprimé concernant mes interrogations. Je voulais parler des 2 rotations d'angle  r*(2pi/p) et q*(2pi/p) ou bien $\alpha^{r}$ et $\alpha^{q}$.

En gros, je ne vois pas comment démontrer que $\alpha^{r}*$ conf et $\alpha^{q}*$ conf sont forcement 2 configurations différentes quand r et q le sont.

Sur tes suggestions, je comprends bien que l'inverse de la rotation   $\alpha^{r}*$ et la rotation $\alpha^{q}*$ avec ur+vr=1 (les solutions u et v sont modulo p => on prend un q dans [0,p-1]). Mais cela ne concerne que le groupe, et non pas les actions sur l'ensemble des confs.

J'espère avoir été clair...

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 464

Re : Preuve de $\binom{pa}{pb}\equiv \binom{a}{b} \left [ p \right ] $

Eh bien non, ce que tu écris est incompréhensible pour moi (et ton ur+vr=1 n'arrange rien).
Soit [tex]C[/tex] une configuration. Je reprends ta notation [tex]\alpha[/tex] pour la rotation de [tex]1/p[/tex] tour dans le sens direct.
Soient [tex]q[/tex] et [tex]r[/tex] deux entiers tels que [tex]0\leq q<r<p[/tex], de sorte que [tex]\alpha^q[/tex] et [tex]\alpha^r[/tex] sont deux éléments différents du groupe engendré par [tex]\alpha[/tex]. Si [tex]\alpha^q(C)=\alpha^r(C)[/tex], alors [tex]C=\alpha^{r-q}(C)[/tex] et par l'argument utilisant l'identité de Bézout que j'ai donné plus haut on en déduit [tex]C=\alpha(C)[/tex]. Donc [tex]C[/tex] est invariante par tout le groupe des rotations engendré par [tex]\alpha[/tex], et est une réunion de couronnes.
Non, toujours pas ?

Jippy13011

Membre

Inscription : 16-09-2023

Messages : 21

Re : Preuve de $\binom{pa}{pb}\equiv \binom{a}{b} \left [ p \right ] $

Effectivement, c'est pas clair ce que j'ai écrit (la prochaine fois, je prendrai plus de temps à me relire).

Je voulais dire que la réciproque de la rotation $\alpha ^{r} $ est la rotation  $\alpha ^{s}$ où s <p et s vérifie ur+vs=1 avec u,v entiers relatifs.

Maintenant, oui, ton explication m'éclaire sur la compréhension de la démo. Si 2 rotations différentes appliquées à une conf donnent la même conf alors cela implique que $\alpha$  laisse invariant cette même conf ce qui n'est pas possible ....

Merci Michel.

Michel Coste

Membre Expert

Inscription : 05-10-2018

Messages : 1 464

Re : Preuve de $\binom{pa}{pb}\equiv \binom{a}{b} \left [ p \right ] $

Avec plaisir.
Mais je vais te reprendre une nouvelle fois, au risque que tu te sentes harcelé !

Je voulais dire que la réciproque de la rotation [tex]\alpha^r[/tex] est la rotation  [tex]\alpha^s[/tex] où s <p et s vérifie ur+vs=1 avec u,v entiers relatifs.

Absolument pas, ça ne va pas pour de multiples raisons.
La réciproque de la rotation [tex]\alpha^r[/tex] est simplement [tex]\alpha^{-r}[/tex], ou [tex]\alpha^{p-r}[/tex] si tu préfères.
Ce qui se passe, si [tex]0<r<p[/tex], c'est qu'on a une identité de Bézout [tex]ur+vp=1[/tex] (l'identité de Bézout que tu écris ne fait pas sens). On a alors [tex]\left(\alpha^r\right)^u=\alpha^{ur}=\alpha[/tex], ce qui montre qu'une configuration invariante par [tex]\alpha^r[/tex] l'est forcément aussi par [tex]\alpha[/tex] (je sais, je me répète, mais je ne sais pas si tu l'as bien compris).

Jippy13011

Membre

Inscription : 16-09-2023

Messages : 21

Re : Preuve de $\binom{pa}{pb}\equiv \binom{a}{b} \left [ p \right ] $

Et la lumière fut !

Jippy13011

Membre

Inscription : 16-09-2023

Messages : 21

Re : Preuve de $\binom{pa}{pb}\equiv \binom{a}{b} \left [ p \right ] $

Voilà en fait ce que je voulais écrire...Bezout est vraiment utile et puissant.

$ru+qp=1 \Rightarrow \alpha^{ru+qp} =\alpha^{ru} *  \alpha^{qp} = \alpha $

$ \text{Ainsi} \quad \alpha^{ru} *  \alpha^{qp} =\alpha \Rightarrow
\left(\alpha^r\right)^u=\alpha^{ur}=\alpha  \quad
  \text{car} \ \alpha^{qp} = Id$

Encore merci Michel