Critère de divisibilité
En mathématiques et plus précisément en arithmétique modulaire, un critère de divisibilité est une particularité d'un entier permettant de déterminer si ce nombre est divisible par un autre. Malgré leur apparence de « recette de cuisine », les critères de divisibilité sont fondés sur des démonstrations mathématiques ; il est possible d'en trouver pour n'importe quel nombre grâce aux congruences.
Jalons historiques
La recherche de divisibilité est une activité classique en arithmétique et les critères de divisibilité y apparaissent fréquemment, redécouverts plusieurs fois dans diverses cultures et diverses périodes. Outre les critères classiques de divisibilité par 2 et 5, on voit apparaitre assez tôt des critères de divisibilité par 7, 9, 11, 13.
On trouve ainsi dans le Talmud de Babylone (VIe siècle), l'utilisation de la propriété suivante[1] :
- et ont même reste dans la division par 7;
Selon Fontés[2], les mathématiciens arabes connaissaient le critère de divisibilité par 9 et l'utilisaient dans la preuve par neuf.
En Europe, on a trace d'une réduction du nombre par la gauche pour une divisibilité par 7 chez Pierre Forcadel, qui pose, dans son arithmétique de 1556, la règle suivante : pour obtenir le reste d'un nombre dans la division par 7, prendre le chiffre le plus à gauche, le multiplier par 3 et l'ajouter au chiffre suivant[3].
Blaise Pascal, dans son De Numeris Multiplicibus[4] de 1654, propose un test de divisibilité général par D consistant à remplacer dans l'écriture d'un nombre chaque puissance de 10 par son reste dans la division par D. Il remarque également que son critère s'applique aussi à une écriture dans toute autre base que la décimale.
En 1738, Georg Wolfgang Krafft expose[5] des critères de divisibilité par 7 et propose à cette occasion une méthode de réduction par la droite[6]: il remarque que, si , alors le nombre égal à est divisible par 7 si et seulement si est divisible par 7.
En 1795, Joseph-Louis Lagrange[7] reprend le critère de Pascal et l'élargit en proposant de prendre, non pas le reste de la puissance de 10, mais l'entier relatif le plus proche de 0 ayant même reste[8], de telle sorte que les coefficients soient, en valeur absolue, plus petits que D/2[9].
Le XIXe siècle voit fleurir de nombreuses publications sur les critères de divisibilité par réduction par la droite. En 1834, Carl Johan Hill (sv) présente, sans démonstration et en se référant à Krafft[10], de multiples critères de réduction par la gauche[11] (divisibilité par 13, 17, 59, 73, 97, 103, 137, ...) ou par la droite[12] (divisibilité par 7, 11, 29,...) par tranches de un, deux ou trois chiffres. En 1844, August Leopold Crelle publie dans son Journal[13] des résultats de théorie des nombres et donne un critère général de divisibilité dans l'écriture dans une base A quelconque dont peuvent se déduire les méthodes de réductions par la gauche et par la droite[14]: pour un nombre , et pour un diviseur , si les entiers et sont liés par la relation alors, en posant , on a est divisible par si et seulement si l'est. Le cas donne un critère de réduction par la gauche et le cas en donne un par la droite. Ce cas général permet en outre d'opérer des réductions par tranches. En 1860, A. Zbikowski présente et démontre explicitement le critère par réduction (soustractive) par la droite[15] et fournit les coefficients pour tous les diviseurs premiers jusqu'à 101. En 1888, M. Loir présente et démontre la même règle et fournit la méthode pour trouver le coefficient à appliquer selon le chiffre des unités du diviseur[16].
Notations
Par la suite, on notera , le nombre dont la divisibilité par est étudiée.
Méthode de Pascal
On calcule à l'avance le reste de chaque puissance de 10 dans la division par (on le diminue éventuellement[17] de s'il dépasse ). Il n'y a qu'un nombre fini de restes à calculer car ce « ruban » de restes est périodique : en effet il n'existe qu'un nombre fini de restes possibles et on retombe donc nécessairement sur un reste déjà trouvé, à partir duquel la suite des restes est périodique[17]. On peut alors remplacer, dans l'écriture du nombre A, chaque puissance de 10 par son reste : le nombre obtenu aura toujours même reste que dans la division par .
Cette méthode fournit non seulement un critère de divisibilité mais donne également un moyen de connaitre le reste de la division de par .
Elle se généralise à l'écriture de dans toute base[18] en cherchant les restes des puissances de dans la division par
Critères classiques
Cette méthode fournit les critères de divisibilité les plus classiques
- par 2 : toutes les puissances de 10 d'exposant non nul ayant pour reste 0, il vient :
Un nombre est pair, c'est-à-dire divisible par 2, si et seulement si[19] son chiffre des unités est 0, 2, 4, 6 ou 8.
- par 3: toutes les puissances de 10 ayant pour reste 1 dans la division par 3, il vient
Un nombre est divisible par 3 si et seulement si[20] la somme de ses chiffres est divisible par 3
- Par 5: toutes les puissances de 10 d'exposant non nul ayant pour reste 0, il vient :
Un nombre est divisible par 5, si et seulement si[19] son chiffre des unités est 0,ou 5.
- par 9: toutes les puissances de 10 ayant pour reste 1 dans la division par 9, il vient
Un nombre est divisible par 9 si et seulement si[20] la somme de ses chiffres est divisible par 9
- par 11: Les puissances de 10 ayant pour reste alternativement 1 et 10 (que l'on peut réduire à -1) dans la division par 11, il vient
Un nombre est divisible par 11 si et seulement si[21] la différence entre la somme de ses chiffres de rang pair et la somme de ses chiffres de rang impair est divisible par 11
- par 7 : On utilise la clé de divisibilité : 1, 3, 2, −1, −3, −2. Celle-ci s'obtient par exemple à partir des restes de la division[22] de 1, 10, 100, etc. par 7, auxquels on retranche 7 lorsqu'ils dépassent 3. On multiplie par le chiffre correspondant de la clé chaque chiffre du nombre à analyser en commençant par les unités.
Un nombre est divisible par 7 si et seulement si[22] le nombre obtenu à l'issue de cette somme-produit est divisible par 7
- Pour vérifier, par exemple, que 826 413 est divisible par 7, on regarde si le nombre 3 × 1 + 1 × 3 + 4 × 2 + 6 × (−1) + 2 × (−3) + 8 × (−2) est divisible par 7. La valeur absolue de ce nombre est 14, qui est bien divisible par 7 (on peut utiliser la table de multiplication ou une nouvelle fois le ruban de Pascal : 4 × 1 + 1 × 3 = 7).
- Inversement, 19 231 n'est pas divisible par 7 car 1 × 1 + 3 × 3 + 2 × 2 + 9 × (−1) + 1 × (−3) = 1 + 9 + 4 – 9 – 3 = 2 n'est pas un multiple de 7.
Regroupement par blocs
Dans le cas où premier avec 10, pour un très grand nombre, on peut raccourcir ce travail en le faisant précéder d'une réduction de ce nombre. On cherche d'abord le plus petit entier r > 0 tel que 10r ≡ ±1 mod D (pour 10r ≡ +1 mod D, cet entier r est la période du ruban de Pascal en base dix), puis on applique la méthode du « ruban de Pascal en base 10r », base pour laquelle la clé de divisibilité est très simple :
L'entier A peut se découper en nr blocs de r chiffres ceci correspond à l'écriture de A dans la base . Et l'on applique alors la méthode de Pascal.
- si 10r est congru à 1 modulo D, l'entier A a même reste que la somme de ces nr blocs.
- si 10r est congru à –1 modulo D, l'entier A a même reste que la somme alternée de ces nr blocs : A0 – A1 + A2 – ....
On obtient ainsi un nombre B dont l'ordre de grandeur est voisin de 10r.
106 ≡ 1 mod 7 donc pour la divisibilité par 7, on découpera en tranches de 6.
1 000 109 826 303 est divisible par 7 si et seulement si 826 303 + 109 + 1, c'est-à-dire 826 413, l'est. Une fois le nombre ainsi réduit, l'une ou l'autre des deux méthodes précédentes montre qu'il est divisible par 7.
On peut réduire davantage la taille du nombre en remarquant que 103 ≡ –1 mod 7 et que l'on peut faire la somme alternée des blocs de 3 chiffres :
1 000 109 826 303 est divisible par 7 si et seulement si 303 – 826 + 109 – 0 + 1, c'est-à-dire –413, l'est.On recherche la divisibilité de 413 par la méthode de son choix..
Réduction par la droite
Ces méthodes consiste à prendre le nombre de dizaines de , c'est-à-dire à supprimer le chiffre des unités, et à lui ajouter le chiffre des unités multiplié par le bon coefficient permettant de conserver le caractère de divisibilité. Elles ne s'appliquent que pour des diviseurs premiers avec 10, c'est-à-dire des diviseurs se terminant par 1, 3, 7, ou 9, et ne conservent pas le reste.
Méthode soustractive
Critère
Puisque est premier avec 10, il existe deux entiers naturels () et tels que (d'après le Théorème de Bézout).
Pour , on pose . est divisible par si et seulement si l'est aussi[16]
En général, cette technique permet de diminuer la taille du nombre et peut se réitérer avec le nombre jusqu'à reconnaitre un multiple ou un non-multiple de .
Pour la divisibilité par 7, on peut remarquer que ce qui fournit et .
Ensuite, pour vérifier, par exemple, que 826 413 est divisible par 7 :
826 413 est divisible par 7 si et seulement si 82 641 – 2 × 3, c'est-à-dire 82 635, l'est ;
82 635 est divisible par 7 si et seulement si 8 263 – 2 × 5, c'est-à-dire 8 253, l'est ;
8 253 est divisible par 7 si et seulement si 825 – 2 × 3, c'est-à-dire 819, l'est ;
819 est divisible par 7 si et seulement si 81 – 2 × 9, c'est-à-dire 63, l'est ;
enfin, 63 est divisible par 7 car 6 – 2 × 3, c'est-à-dire 0, l'est.
Recherche des coefficients
Il s'agit de trouver le plus petit multiple de qui se termine par 1. L'observation du chiffre des unités de permet de distinguer 4 cas[16]:
Ainsi pour la divisibilité par 23, on retranchera 16 (= 2 × 7 + 2) fois le chiffre des unités au nombre de dizaines.
Critère d'arrêt
Le processus itéré fournit une suite d'entiers La suite est décroissante tant que
Il suffit donc de poursuivre le calcul tant que la suite est décroissante et de comparer le dernier nombre aux premiers multiples de
On cherche la divisibilité de 24 213 par 33. On sait que et
La suite cesse d'être décroissante, et donc 189 n'est pas multiple de 33 et 24 213 non plus.
On cherche la divisibilité de 17 603 par 29. On sait que et
La suite cesse d'être décroissante, donc 17 603 est divisible par 29
Méthode additive
Critère
Puisque est premier avec 10, il existe deux entiers naturels () et tels que . Soit encore
Pour , on pose . est divisible par si et seulement si l'est aussi[23].
En général, cette technique permet de diminuer la taille du nombre et peut se réitérer avec le nombre jusqu'à reconnaitre un multiple ou un non-multiple de .
Pour la divisibilité par 19, on peut remarquer que ce qui fournit et .
Ensuite, pour vérifier, par exemple, que 2 508 est divisible par 19 :
2 508 est divisible par 19 si et seulement si 250 + 2 × 8, c'est-à-dire 266, l'est ;
266 est divisible par 19 si et seulement si 26 + 2 × 6, c'est-à-dire 38, l'est.
38 est divisible par 19 si et seulement si 3 + 2 × 8, c'est-à-dire 19, l'est.
Donc 2 508 est divisible par 19
Recherche des coefficients
Il s'agit de trouver le plus petit multiple de qui se termine par 9. L'observation du chiffre des unités de permet de distinguer 4 cas[24]:
Ainsi pour la divisibilité par 23, on ajoutera 7 (= 2 × 3 + 1) fois le chiffre des unités au nombre de dizaines.
Critère d'arrêt
Le processus itéré fournit une suite d'entiers La suite est décroissante tant que
Il suffit donc de poursuivre le calcul tant que la suite est décroissante et de comparer le dernier nombre aux premiers multiples de
On cherche la divisibilité de 3 136 par 7. On sait que et
La suite cesse d'être décroissante, donc 3 136 est divisible par 7.
On cherche la divisibilité de 27 603 par 29. On sait que et
- qui n'est pas multiple de 29 donc 27 603 n'est pas divisible par 29.
Démonstration pour un nombre quelconque
De manière générale, pour déterminer si un nombre A est divisible par D, on procède en plusieurs étapes :
- on décompose D sous la forme D' × 2q × 5p où D' est premier avec 10 ;
- à la suite de la transitivité de la division euclidienne et par conséquent du lemme de Gauss (si a | c, b | c et pgcd(a,b) = 1, alors ab | c), D divise A si et seulement si D', 2q et 5p divisent A ;
- optionnellement, si l'on dispose d'une factorisation de D en produit de facteurs deux à deux premiers entre eux, on peut de même réduire le problème de la divisibilité par D aux problèmes analogues pour ces facteurs. Par exemple : A est divisible par 63 si et seulement s'il est divisible par 9 et par 7.
Divisibilité par 2q
A est divisible par 2q si et seulement si le nombre formé par les q premiers chiffres (en partant de l'unité) est divisible par 2q.
Exemple : 79 532 512 est divisible par 16 (= 24) car 2 512 est divisible par 16.
Démonstration : 10q est multiple de 2q, donc on peut se débarrasser de toute la partie du nombre multiple de 10q.
Divisibilité par 5p
A est divisible par 5p si et seulement si le nombre formé par ses p premiers chiffres (en partant de l'unité) est divisible par 5p.
Exemple : 9 864 375 est divisible par 125 (= 53) car 375 est divisible par 125.
Démonstration : 10p est multiple de 5p, donc on peut se débarrasser de toute la partie du nombre multiple de 10p.
Divisibilité par D' premier avec 10
On peut utiliser un des critères décrits précédemment (méthode de Pascal ou réduction par la droite)
Remarque sur la complexité algorithmique
In fine, on peut trouver de cette manière, pour tout M, un critère de divisibilité par M. Il faut d'abord remarquer qu'un critère général itératif existe : un nombre A est divisible par M si le reste de la division euclidienne de A par M est nul. Un tel calcul s'effectue en un nombre d'opérations déterminé par le nombre de chiffres de A (la complexité est linéaire).
Les algorithmes présentés ici sont en fait des variantes de cet algorithme général : on a vu qu'on les obtenait via un calcul modulaire, qui repose sur la notion de division euclidienne. Leur complexité est donc linéaire : à chaque étape de calcul, on est ramené à tester la division par m d'un nombre ayant un chiffre de moins que le nombre précédent, et le nombre d'étapes total est de l'ordre du nombre de chiffres de A. Pour un calcul à la main en base dix, du moins pour les petits diviseurs m, l'avantage de ces méthodes par rapport à la méthode générale est d'éviter les calculs intermédiaires de division.
Toutefois ces méthodes ne fournissent qu'un critère de divisibilité, alors que la méthode générale fournit le quotient et le reste.
Bibliographie
- (en) Leonard Eugene Dickson, History of the Theory of Numbers (en), vol. 1, [détail des éditions] (lire en ligne), chap. XII (« Criteria for divisibility by a given number. »), p. 337-346;
- (en) Eric L. McDowel, « Divisibility Tests: A History and User's Guide », Convergence, Mathematical association of america, (DOI 10.4169/convergence20180513, lire en ligne);
- M. Fontés, « Bilan des Caractères de divisibilité », Mémoires de l'Académie des sciences, inscription et belles lettres (Toulouse), t. 5, no 9, , p. 459-465 (lire en ligne);
- Martin Gardner, Le paradoxe du pendu et autres divertissements mathématiques [« The Unexpected Hanging & Other Mathematical Diversions »], Paris, Dunod, , chap. 14 (« Caractères de divisibilité »), p. 156-165 ;
- Eugène Humbert (préf. Jules Tannery), Traité d'arithmétique : à l'usage des élèves de mathématiques élémentaires …, Librairie Nony, (lire en ligne), chap. VI (« Divisibilité »), p. 92-108.
Références
- (en) Eric L. McDowel, « Divisibility Tests: A History and User's Guide - The Beginnings of Divisibility », Convergence, Mathematical association of america, (lire en ligne)
- Fontés 1893, p. 461.
- Fontés 1893, p. 462.
- Voir sur wikisource
- (la) Georg Wolfgang Krafft, « Observationes arithmeticae de septenario », Commentarii Academiae scientiarum imperialis Petropolitanae, vol. VI, , p. 41-45 (lire en ligne)
- Krafft 1738, p. 45.
- Joseph-Louis Lagrange, « Lecons élémentaires sur les mathématiques données à l'École Normale en 1795 », dans Œuvres de lagrange publiées par less soins de M. J.-A. Serret, t. 7, (lire en ligne), p. 204-208
- Lagrange 1795, p. 206.
- Dickson 1919, p. 338.
- (la) Carl Johan Hill, « De factoribus numerorum compositorum dignoscendis », Journal für die reine und angewandte Mathematik, , p. 251-261 (lire en ligne)
- Hill 1834, p. 252-253.
- Hill 1834, p. 254-255.
- (de) August Leopold Crelle, « Encyklopa¨dische une elemantare Darstellung des Theorie der Zahlen », Journal für die reine und angewandte Mathematik, , p. 107-181 (lire en ligne)
- Crelle 1844, p. 125.
- A. Zbikowski, « Note sur la divisbilité des nombres », Bulletin de l'académie Impériale des Sciences de Saint-petersbourg, , p. 151-153 (lire en ligne)
- M. Loir, « Caractère de divisibilité d'un nombre par un nombre premier quelconque », Comptes rendus hebdomadaires des séances de l'académie des sciences, t. CVI, no 15, , p. 1070-1071 (lire en ligne)
- Humbert 1893, p. 104.
- Humbert 1893, p. 106.
- Humbert 1893, p. 93.
- Humbert 1893, p. 95.
- Humbert 1893, p. 96.
- Humbert 1893, p. 103.
- (en) Eric L. McDowel, « Divisibility Tests: A History and User's Guide - Zbikowski Divisibility Tests », Convergence, Mathematical association of america, (lire en ligne) - Addition style Zbikowski tests
- Suite A333448 dans OEIS
Liens externes
- (en) Edwin O'Shea, « Divisibility Tests Unified: Stacking the Trimmings for Sums »,
- (en) Marc Renault, « Stupid Divisibility Tricks — 101 Ways to Stupefy Your Friends », Math Horizons (en), vol. 14, no 2, , p. 18-21, 42 (lire en ligne)