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 :

$100c+u$ et $2c+u$ ont même reste dans la division par 7;

Selon Fontés, 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 ajouter le reste dans la division euclidienne de ce nombre par 7 au chiffre suivant.

Blaise Pascal, dans son De Numeris Multiplicibus 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 des critères de divisibilité par 7 et propose à cette occasion une méthode de réduction par la droite: il remarque que, si $10c+b=3m$, alors le nombre $N$ égal à $10a+b$ est divisible par 7 si et seulement si $a+m-c$ est divisible par 7.

En 1795, Joseph-Louis Lagrange 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, de telle sorte que les coefficients soient, en valeur absolue, plus petits que D/2.

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, de multiples critères de réduction par la gauche (divisibilité par 13, 17, 59, 73, 97, 103, 137, ...) ou par la droite (divisibilité par 7, 11, 29,...) par tranches de un, deux ou trois chiffres. En 1844, August Leopold Crelle publie dans son Journal 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: pour un nombre $Z=x_{m}A^{m}+x_{m-1}A^{m-1}+\cdots +x_{1}A+x_{0}$, et pour un diviseur $s$, si les entiers $n$ et $r$ sont liés par la relation $nA=r+ks$ alors, en posant $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 $Z$ est divisible par $s$ si et seulement si $z$ l'est. Le cas $n=\pm 1$ donne un critère de réduction par la gauche et le cas $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 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.

Notations

Par la suite, on notera $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 $D$ est étudiée.

Méthode de Pascal

On calcule à l'avance le reste de chaque puissance de 10 dans la division par $D$ (on le diminue éventuellement de $D$ s'il dépasse $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. 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 $A$ dans la division par $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 $A$ par $D$.

Elle se généralise à l'écriture de $A$ dans toute base $B$ en cherchant les restes des puissances de $B$ dans la division par $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 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 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 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 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 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 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 le nombre obtenu à l'issue de cette somme-produit est divisible par 7

Exemples :

• 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ù $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 $A=\sum _{i=0}^{n_{r}-1}A_{i}10^{ri}$ ceci correspond à l'écriture de A dans la base $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.

Exemple :

10⁶ ≡ 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 10³ ≡ –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 $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 $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 $D$ est premier avec 10, il existe deux entiers naturels $\alpha$ ($\alpha <10$) et $\beta$ tels que $\alpha D-\beta 10=1$ (d'après le Théorème de Bézout).

Pour $A=10d+a_{0}$, on pose $A'=d-\beta a_{0}$. $A$ est divisible par $D$ si et seulement si $A'$ l'est aussi

Démonstration

$10A'=10d-10\beta a_{0}=10d+a_{0}-\alpha Da_{0}=A-\alpha Da_{0}$

Donc $A$ est multiple de $D$ si seulement si $10A'$ est multiple de $D$. Comme 10 est premier avec $D$, $10A'$ est multiple de $D$ si et seulement si $A'$ est multiple de $D$

En général, cette technique permet de diminuer la taille du nombre et peut se réitérer avec le nombre $|A'|$ jusqu'à reconnaitre un multiple ou un non-multiple de $D$.

Exemple :

Pour la divisibilité par 7, on peut remarquer que $3\times 7-2\times 10=1$ ce qui fournit $\alpha =3$ et $\beta =2$.

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 $D$ qui se termine par 1. L'observation du chiffre des unités de $D$ permet de distinguer 4 cas:

• $D=10m+1\quad \alpha =1\quad \beta =m$
• $D=10m+3\quad \alpha =7\quad 7D=10\times 7m+20+1\quad \beta =7m+2$
• $D=10m+7\quad \alpha =3\quad 3D=10\times 3m+20+1\quad \beta =3m+2$
• $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 $A_{0}=A,\,A_{1}=|A'_{0}|,\cdots ,\,A_{n+1}=|A'_{n}|,\cdots$ La suite est décroissante tant que $A_{n}\geq \alpha D$

Démonstration

On sait que $A'_{n}={\frac {A_{n}-\alpha Da_{0}}{10}}$ (voir démonstration précédente). Donc $A'_{n}<A_{n}$

• Si $A'_{n}\geq 0$, on a bien $A_{n+1}<A_{n}$
• Si $A'_{n}<0$, on a $A_{n+1}=-A'_{n}={\frac {\alpha Da_{0}-A_{n}}{10}}\leq {\frac {A_{n}a_{0}-A_{n}}{10}}$. Or ${\frac {A_{n}a_{0}-A_{n}}{10}}={\frac {a_{0}-1}{10}}A_{n}<A_{n}$. Donc $A_{n+1}<A_{n}$

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

Exemple 1 :

On cherche la divisibilité de 24 213 par 33. On sait que $\alpha =7$ et $\beta =23$

$A_{1}=2421-3\times 23=2352$

$A_{2}=242-5\times 23=189$

$A_{3}=|18-9\times 23|=189$

La suite cesse d'être décroissante, $6\times 33=198$ et $5\times 33=165$ donc 189 n'est pas multiple de 33 et 24 213 non plus.

Exemple 2 :

On cherche la divisibilité de 17 603 par 29. On sait que $\alpha =9$ et $\beta =26$

$A_{1}=1760-3\times 26=1682$

$A_{2}=168-2\times 26=116$

$A_{3}=|11-6\times 26|=145$

La suite cesse d'être décroissante, $4\times 29=116$ donc 17 603 est divisible par 29

Méthode additive

Critère

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

Pour $A=10d+a_{0}$, on pose $A'=d+\beta a_{0}$. $A$ est divisible par $D$ si et seulement si $A'$ l'est aussi.

Démonstration

$10A'=10d+10\beta a_{0}=10d+a_{0}+\alpha Da_{0}=A+\alpha Da_{0}$

Donc $A$ est multiple de $D$ si seulement si $10A'$ est multiple de $D$. Comme 10 est premier avec $D$, $10A'$ est multiple de $D$ si et seulement si $A'$ est multiple de $D$

En général, cette technique permet de diminuer la taille du nombre et peut se réitérer avec le nombre $A'$ jusqu'à reconnaitre un multiple ou un non-multiple de $D$.

Exemple :

Pour la divisibilité par 19, on peut remarquer que $19=1\times 10+9$ ce qui fournit $\alpha =1$ et $\beta =2$.

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 $D$ qui se termine par 9. L'observation du chiffre des unités de $D$ permet de distinguer 4 cas:

• $D=10m+1\quad \alpha =9\quad \beta =9m$
• $D=10m+3\quad \alpha =3\quad 3D=10\times 3m+9\quad \beta =3m+1$
• $D=10m+7\quad \alpha =7\quad 3D=10\times 7m+40+9\quad \beta =7m+5$
• $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 $A_{0}=A,\,A_{1}=A'_{0},\cdots ,\,A_{n+1}=A'_{n},\cdots$ La suite est décroissante tant que $A_{n}>\alpha D$

Démonstration

On sait que $A'_{n}={\frac {A_{n}+\alpha Da_{0}}{10}}$ (voir démonstration précédente). Donc

Puisque $A_{n}>\alpha D$, on a $A_{n+1}\leq {\frac {A_{n}+A_{n}a_{0}}{10}}\leq A_{n}$. Donc $A_{n+1}<A_{n}$

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

Exemple 1 :

On cherche la divisibilité de 3 136 par 7. On sait que $\alpha =7$ et $\beta =5$

$A_{1}=313+6\times 5=343$

$A_{2}=34+3\times 5=49$

$A_{3}=4+9\times 5=49$

La suite cesse d'être décroissante, $7\times 7=49$ donc 3 136 est divisible par 7.

Exemple 2 :

On cherche la divisibilité de 27 603 par 29. On sait que $\alpha =1$ et $\beta =3$

$A_{1}=2760+3\times 3=2769$

$A_{2}=276+9\times 3=303$

$A_{3}=30+3\times 3=39$

$A_{4}=3+9\times 3=30$ qui n'est pas multiple de 29 donc 27 603 n'est pas divisible par 29.

Réduction par la gauche

La méthode consiste, pour les diviseurs inférieurs à 10, à multiplier le chiffre le plus à gauche par le complément à 10 du diviseur et à en ajouter le résultat au chiffre suivant, et en réitérant l'opération, on obtient le reste de la division. Comme de nombreuses méthodes, elle consiste à retirer des multiples du diviseur jusqu'à épuisement afin d'obtenir le reste de la division. Par exemple pour 7, on multipliera par 3 :

17381 devient 10381 puis 3381, 1281, 581, 231, 91, 28, 14, 7 donc divisible par 7 (qu'on aurait pu reconnaitre dès 28 voire 91).

On notera que, pour 9, il suffit de multiplier par 1 le chiffre à gauche et d'ajouter au suivant et en réitérant on obtient la règle classique.

Pour des diviseurs un peu supérieurs à 10, le "complément" sera pris négatif. Ainsi, pour 11, on multipliera par -1 ce qui redonne la règle déjà rencontrée.

On peut tenter de multiplier par -3 pour 13 ainsi :

avec 312 : -9+1=-8 et -3 x (-8) + 2 = 26 divisible.

et avec 1 664 : -3+6 = 3 , -9+6 =-3 et 9+4 = 13 divisible.

Enfin la méthode peut s'appliquer au delà des diviseurs proches de 10, elle est efficiente pour des valeurs proches de 100 voire de 1000.

Par exemple, pour une divisibilité par 99, proche de 100, on séquence les nombres par 2 chiffres en partant de la droite ainsi

pour 407 on fait 4|07 et 4+7 =11. Le reste de la division par 99 est 11. Ce nombre est divisible par 11 puisque 99 l'est aussi.

Pour 3 432, on aura 34+32=66 également divisible par 11.

La divisibilité par 98 mène plus rapidement à celle par 7 (98=7x14) avec des multiplications par 100 - 98=2.

Avec 17 381 soit 1|73|81, on aura 73+2=75, 150+81=231, 4+31=35 reste de la division par 98 divisible par 7.

Avec 1001 =7x11x13 on accélère avec un multiplicateur (-1) les nombres séquencés par 3 chiffres mais il faut généralement finir par un critère plus standard avec un reste à 3 chiffres :

17 381 soit 17|381 donne 381-17=364 on passe la règle précédente pour 7 soit 64+6 = 70 divisible par 7 ou bien pour 13  : (-3)x3+6 = -3 et (-3)x(-3)+4=13 donc divisible par 13

Mise en place des critères pour un diviseur 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.

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)