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 (VI^e siècle), l'utilisation de la propriété suivante^[1] :

${\displaystyle 100c+u}$ et ${\displaystyle 2c+u}$ 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 ${\displaystyle 10c+b=3m}$, alors le nombre ${\displaystyle N}$ égal à ${\displaystyle 10a+b}$ est divisible par 7 si et seulement si ${\displaystyle a+m-c}$ 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 XIX^e 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 ${\displaystyle Z=x_{m}A^{m}+x_{m-1}A^{m-1}+\cdots +x_{1}A+x_{0}}$, et pour un diviseur ${\displaystyle s}$, si les entiers ${\displaystyle n}$ et ${\displaystyle r}$ sont liés par la relation ${\displaystyle nA=r+ks}$ alors, en posant ${\displaystyle z=x_{m}r^{m}+x_{m-1}r^{n-1}n+\cdots +x_{1}r^{1}n^{m-1}+x_{0}n^{m}}$, on a ${\displaystyle Z}$ est divisible par ${\displaystyle s}$ si et seulement si ${\displaystyle z}$ l'est. Le cas ${\displaystyle n=\pm 1}$ donne un critère de réduction par la gauche et le cas ${\displaystyle r=\pm 1}$ 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 ${\displaystyle A={\overline {a_{n}a_{n-1}\cdots a_{1}a_{0}}}=\sum _{k=0}^{n}a_{k}10^{k}=10d+a_{0}}$, le nombre dont la divisibilité par ${\displaystyle D}$ est étudiée.

Méthode de Pascal

On calcule à l'avance le reste de chaque puissance de 10 dans la division par ${\displaystyle D}$ (on le diminue éventuellement^[17] de ${\displaystyle D}$ s'il dépasse ${\displaystyle D/2}$). 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 ${\displaystyle A}$ dans la division par ${\displaystyle D}$.

Cette méthode fournit non seulement un critère de divisibilité mais donne également un moyen de connaitre le reste de la division de ${\displaystyle A}$ par ${\displaystyle D}$.

Elle se généralise à l'écriture de ${\displaystyle A}$ dans toute base^[18] ${\displaystyle B}$ en cherchant les restes des puissances de ${\displaystyle B}$ dans la division par ${\displaystyle D}$

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

Regroupement par blocs

Dans le cas où ${\displaystyle D}$ 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 10^r ≡ ±1 mod D (pour 10^r ≡ +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 10^r », base pour laquelle la clé de divisibilité est très simple :

L'entier A peut se découper en n_r blocs de r chiffres ${\displaystyle A=\sum _{i=0}^{n_{r}-1}A_{i}10^{ri}}$ ceci correspond à l'écriture de A dans la base ${\displaystyle 10^{r}}$. Et l'on applique alors la méthode de Pascal.

• si 10^r est congru à 1 modulo D, l'entier A a même reste que la somme de ces n_r blocs.
• si 10^r est congru à –1 modulo D, l'entier A a même reste que la somme alternée de ces n_r blocs : A₀ – A₁ + A₂ – ....

On obtient ainsi un nombre B dont l'ordre de grandeur est voisin de 10^r.

Réduction par la droite

Ces méthodes consiste à prendre le nombre de dizaines de ${\displaystyle A}$, 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 ${\displaystyle D}$ 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 ${\displaystyle D}$ est premier avec 10, il existe deux entiers naturels ${\displaystyle \alpha }$ (${\displaystyle \alpha <10}$) et ${\displaystyle \beta }$ tels que ${\displaystyle \alpha D-\beta 10=1}$ (d'après le Théorème de Bézout).

Pour ${\displaystyle A=10d+a_{0}}$, on pose ${\displaystyle A'=d-\beta a_{0}}$. ${\displaystyle A}$ est divisible par ${\displaystyle D}$ si et seulement si ${\displaystyle A'}$ 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 ${\displaystyle |A'|}$ jusqu'à reconnaitre un multiple ou un non-multiple de ${\displaystyle D}$.

Recherche des coefficients

Il s'agit de trouver le plus petit multiple de ${\displaystyle D}$ qui se termine par 1. L'observation du chiffre des unités de ${\displaystyle D}$ permet de distinguer 4 cas^[16]:

• ${\displaystyle D=10m+1\quad \alpha =1\quad \beta =m}$
• ${\displaystyle D=10m+3\quad \alpha =7\quad 7D=10\times 7m+20+1\quad \beta =7m+2}$
• ${\displaystyle D=10m+7\quad \alpha =3\quad 3D=10\times 3m+20+1\quad \beta =3m+2}$
• ${\displaystyle D=10m+9\quad \alpha =9\quad 9D=10\times 9m+80+1\quad \beta =9m+8}$

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 ${\displaystyle A_{0}=A,\,A_{1}=|A'_{0}|,\cdots ,\,A_{n+1}=|A'_{n}|,\cdots }$ La suite est décroissante tant que ${\displaystyle A_{n}\geq \alpha D}$

Il suffit donc de poursuivre le calcul tant que la suite est décroissante et de comparer le dernier nombre aux ${\displaystyle \alpha -1}$ premiers multiples de ${\displaystyle D}$

Méthode additive

Critère

Puisque ${\displaystyle D}$ est premier avec 10, il existe deux entiers naturels ${\displaystyle \alpha }$ (${\displaystyle \alpha <10}$) et ${\displaystyle \beta }$ tels que ${\displaystyle \alpha D-\beta 10=-1}$. Soit encore ${\displaystyle \alpha D=(\beta -1)10+9}$

Pour ${\displaystyle A=10d+a_{0}}$, on pose ${\displaystyle A'=d+\beta a_{0}}$. ${\displaystyle A}$ est divisible par ${\displaystyle D}$ si et seulement si ${\displaystyle A'}$ 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 ${\displaystyle A'}$ jusqu'à reconnaitre un multiple ou un non-multiple de ${\displaystyle D}$.

Recherche des coefficients

Il s'agit de trouver le plus petit multiple de ${\displaystyle D}$ qui se termine par 9. L'observation du chiffre des unités de ${\displaystyle D}$ permet de distinguer 4 cas^[24]:

• ${\displaystyle D=10m+1\quad \alpha =9\quad \beta =9m}$
• ${\displaystyle D=10m+3\quad \alpha =3\quad 3D=10\times 3m+9\quad \beta =3m+1}$
• ${\displaystyle D=10m+7\quad \alpha =7\quad 3D=10\times 7m+40+9\quad \beta =7m+5}$
• ${\displaystyle D=10m+9\quad \alpha =1\quad \beta =m+1}$

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 ${\displaystyle A_{0}=A,\,A_{1}=A'_{0},\cdots ,\,A_{n+1}=A'_{n},\cdots }$ La suite est décroissante tant que ${\displaystyle A_{n}>\alpha D}$

Il suffit donc de poursuivre le calcul tant que la suite est décroissante et de comparer le dernier nombre aux ${\displaystyle \alpha }$ premiers multiples de ${\displaystyle D}$

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' × 2^q × 5^p 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', 2^q et 5^p 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 2^q

A est divisible par 2^q si et seulement si le nombre formé par les q premiers chiffres (en partant de l'unité) est divisible par 2^q.

Exemple : 79 532 512 est divisible par 16 (= 2⁴) car 2 512 est divisible par 16.

Démonstration : 10^q est multiple de 2^q, donc on peut se débarrasser de toute la partie du nombre multiple de 10^q.

Divisibilité par 5^p

A est divisible par 5^p si et seulement si le nombre formé par ses p premiers chiffres (en partant de l'unité) est divisible par 5^p.

Exemple : 9 864 375 est divisible par 125 (= 5³) car 375 est divisible par 125.

Démonstration : 10^p est multiple de 5^p, donc on peut se débarrasser de toute la partie du nombre multiple de 10^p.

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, 1919 [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,‎ mai 2018 (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, n^o 9,‎ 1893, 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, 1971, 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, 1893 (lire en ligne), chap. VI (« Divisibilité »), p. 92-108.

Références

Liens externes

• (en) Edwin O'Shea, « Divisibility Tests Unified: Stacking the Trimmings for Sums », juin 2014
• (en) Marc Renault, « Stupid Divisibility Tricks — 101 Ways to Stupefy Your Friends », Math Horizons (en), vol. 14, n^o 2,‎ 2006, p. 18-21, 42 (lire en ligne)

• Arithmétique et théorie des nombres