Lucas's theorem
Pour un nombre premier p et des entiers naturels m et n, le théorème de Lucas affirme que le coefficient binomial C(m, n), modulo p, est le produit modulo p des coefficients binomiaux formés par les chiffres de même rang des écritures de m et n en base p. Il ramène ainsi le calcul d’un grand coefficient binomial modulo p à de petits calculs chiffre par chiffre.
Contents
What you will learn
- Identifier les hypothèses du théorème binomial de Lucas.
- Calculer un reste modulo 5 en décomposant les indices en base 5.
- Reconnaître les deux autres résultats auxquels le nom de Lucas peut renvoyer.
- Éviter l’application erronée de la règle à un module composé.
In plain terms
Choisir 8 objets parmi 23 donne un très grand nombre de possibilités. Si l’on veut seulement son reste après division par 5, inutile de développer tout le calcul. On écrit 23 et 8 en base 5, puis on compare leurs chiffres placés au même rang.
Le théorème de Lucas transforme ainsi un coefficient binomial imposant en un produit de petits coefficients. Le reste final se lit à partir de ces calculs locaux.
Definition
Au sens strict, le théorème de Lucas est un résultat d’arithmétique sur les coefficients binomiaux. Il a été démontré en 1878 par Édouard Lucas. On choisit un nombre premier noté p, ainsi que deux entiers naturels notés m et n. Le coefficient compte les choix de n éléments parmi m lorsque n ne dépasse pas m.
Les entiers m et n sont écrits en base p. Leurs chiffres, notés respectivement mi et ni, sont compris entre 0 et p − 1. On choisit un rang k assez grand pour couvrir tous leurs chiffres et l’on complète les deux écritures par des zéros à gauche jusqu’à ce rang. Le théorème ramène alors le coefficient initial au produit des coefficients formés chiffre par chiffre :
Les écritures sont complétées à gauche par des zéros si nécessaire. Le nom est ambigu. Il peut aussi désigner le théorème de Gauss-Lucas sur les zéros des polynômes complexes, ou un résultat reliant la suite de Brocot aux fractions continues. Ces deux résultats ne sont pas la règle de calcul binomial.
The principle
Soit p un nombre premier. Si les entiers naturels m et n ont pour chiffres en base p les nombres mi et ni, on choisit un rang k assez grand pour couvrir tous leurs chiffres et l’on complète les deux écritures par des zéros à gauche jusqu’à ce rang. Alors :
Chaque petit coefficient associe deux chiffres de même rang, celui de m au-dessus et celui de n au-dessous. Le produit donne le même reste modulo p que le coefficient initial.
When to use it
La règle demande un module p premier et deux entiers naturels m et n. Leurs écritures doivent utiliser la même base p, avec les chiffres de même rang correctement alignés. Lorsque n dépasse m, on adopte la convention usuelle .
Un module composé bloque cette application directe. Par exemple, modulo 6, les écritures 8 = 126 et 2 = 026 donneraient un produit local égal à 1, alors que . Pour ce petit contre-cas, il faut calculer le coefficient exact puis prendre son reste, au lieu d’appliquer la règle chiffre par chiffre.
A step-by-step example
On cherche le reste modulo 5 du nombre de choix de 8 objets parmi 23. Les données sont donc le nombre total m = 23, le nombre choisi n = 8 et le nombre premier p = 5.
1. On écrit les deux entiers en base 5 : 23 = 435 et 8 = 135.
2. On associe les chiffres de gauche, puis ceux de droite : 4 avec 1, et 3 avec 3.
3. On applique le théorème :
2. On associe les chiffres de gauche, puis ceux de droite : 4 avec 1, et 3 avec 3.
3. On applique le théorème :
Le reste recherché est donc 4. Un contrôle direct reste possible : , et 490 314 laisse bien le reste 4 après division par 5. Le dernier chiffre décimal suffit ici à refaire ce contrôle.
In practice
Pour calculer seulement un reste modulo un nombre premier, on convertit les deux indices en base p et l’on multiplie les petits coefficients correspondants. Cette voie évite de construire le coefficient binomial complet, qui peut être immense.
Pour tester la divisibilité par p, il suffit même de repérer un rang où le chiffre de n dépasse celui de m. Le petit coefficient associé vaut alors zéro, donc le coefficient initial est divisible par p.
Si l’on cherche la valeur exacte et non un reste, le théorème de Lucas ne fournit pas cette valeur. Un calcul par produits simplifiés ou une construction du triangle de Pascal est alors plus approprié.
Not to be confused with
Le théorème de Gauss-Lucas concerne les zéros des polynômes complexes. La présence de polynômes complexes, plutôt que de coefficients binomiaux modulo un nombre premier, tranche immédiatement.
Le résultat de Lucas sur la suite de Brocot relie la première apparition d’un rationnel à la somme des coefficients de sa fraction continue. Il classe des rationnels positifs ; il ne calcule pas un coefficient binomial modulo p.
Limits and pitfalls
Le titre « théorème de Lucas » ne suffit pas toujours à identifier le résultat. Si le contexte parle de zéros de polynômes ou de fractions continues, il faut abandonner l’interprétation binomiale et préciser le théorème visé.
La primalité du module est décisive. Le cas modulo 6 donne déjà un résultat faux avec la règle chiffre par chiffre ; il ne faut donc pas remplacer mécaniquement p par un entier composé.
Les chiffres se comparent à partir des unités. Des écritures de longueurs différentes doivent être complétées par des zéros à gauche ; un décalage d’un rang change les petits coefficients et peut changer le reste.
Dès qu’un chiffre ni dépasse le chiffre mi de même rang, le produit local vaut zéro. Le bon verdict est alors une congruence nulle modulo p, et non l’impossibilité d’appliquer le théorème.
Further reading
La fiche nombre premier précise la propriété du module qui rend possible la règle de Lucas.
Le théorème de Gauss-Lucas développe l’autre sens fréquent du nom dans le cadre des polynômes complexes.
La suite de Brocot montre où apparaît le rationnel évoqué par le troisième résultat attribué à Lucas.
La fiche Fraction continue donne le développement dont la somme des coefficients fixe cet indice d’apparition.
Explore mathematics differently
Discover our magazines, podcasts and games to explore mathematics differently.
See our offers