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. Modèle:Voir

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 (Modèle:S-), l'utilisation de la propriété suivante :

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

Selon FontésModèle:Sfn, 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 suivantModèle:Sfn.

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 droiteModèle:Sfn: 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 resteModèle:Sfn, de telle sorte que les coefficients soient, en valeur absolue, plus petits que D/2Modèle:Sfn.

Le Modèle:S- voit fleurir de nombreuses publications sur les critères de divisibilité par réduction par la droite. En 1834, Modèle:Lien présente, sans démonstration et en se référant à Krafft, de multiples critères de réduction par la gaucheModèle:Sfn (divisibilité par 13, 17, 59, 73, 97, 103, 137, ...) ou par la droiteModèle:Sfn (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 droiteModèle:Sfn: Modèle:Retrait 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

Modèle:Article détaillé On calcule à l'avance le reste de chaque puissance de 10 dans la division par $D$ (on le diminue éventuellementModèle:Sfn 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ériodiqueModèle:Sfn. 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 baseModèle:Sfn $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 :

• par 3: toutes les puissances de 10 ayant pour reste 1 dans la division par 3, il vient

• Par 5: toutes les puissances de 10 d'exposant non nul ayant pour reste 0, il vient :

• par 9: toutes les puissances de 10 ayant pour reste 1 dans la division par 9, il vient

• 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

• 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 divisionModèle:Sfn 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.

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 10Modèle:Exp ≡ ±1 mod D (pour 10Modèle:Exp ≡ +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 10Modèle:Exp », base pour laquelle la clé de divisibilité est très simple :

L'entier A peut se découper en nModèle:Ind blocs de r chiffres Modèle:Retrait ceci correspond à l'écriture de A dans la base $10^r$. Et l'on applique alors la méthode de Pascal.

• si 10Modèle:Exp est congru à 1 modulo D, l'entier A a même reste que la somme de ces nModèle:Ind blocs.
• si 10Modèle:Exp est congru à –1 modulo D, l'entier A a même reste que la somme alternée de ces nModèle:Ind blocs : Modèle:Formule.

On obtient ainsi un nombre B dont l'ordre de grandeur est voisin de 10Modèle:Exp.

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^{\prime }=d-\beta a_0$. $A$ est divisible par $D$ si et seulement si $A^{\prime }$ l'est aussi Modèle:Démonstration

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

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\alpha =1\beta =m$
• $D=10m+3\alpha =77D=10\times 7m+20+1\beta =7m+2$
• $D=10m+7\alpha =33D=10\times 3m+20+1\beta =3m+2$
• $D=10m+9\alpha =99D=10\times 9m+80+1\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{\text{'}}_0|,\cdots ,A_{n+1}=|A{\text{'}}_n|,\cdots$ La suite est décroissante tant que $A_n\ge \alpha D$ Modèle:Démonstration

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$

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^{\prime }=d+\beta a_0$. $A$ est divisible par $D$ si et seulement si $A^{\prime }$ l'est aussi. Modèle:Démonstration

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

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\alpha =9\beta =9m$
• $D=10m+3\alpha =33D=10\times 3m+9\beta =3m+1$
• $D=10m+7\alpha =73D=10\times 7m+40+9\beta =7m+5$
• $D=10m+9\alpha =1\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{\text{'}}_0,\cdots ,A_{n+1}=A{\text{'}}_n,\cdots$ La suite est décroissante tant que $A_n>\alpha D$ Modèle:Démonstration

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$

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 DModèle:' × 2Modèle:Exp × 5Modèle:Exp où DModèle:' 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 DModèle:', 2Modèle:Exp et 5Modèle:Exp 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 2Modèle:Exp

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

Exemple : Modèle:Nombre est divisible par 16 (= 2Modèle:4) car Modèle:Nombre est divisible par 16.

Démonstration : 10Modèle:Exp est multiple de 2Modèle:Exp, donc on peut se débarrasser de toute la partie du nombre multiple de 10Modèle:Exp.

Divisibilité par 5Modèle:Exp

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

Exemple : Modèle:Nombre est divisible par 125 (= 5Modèle:3) car 375 est divisible par 125.

Démonstration : 10Modèle:Exp est multiple de 5Modèle:Exp, donc on peut se débarrasser de toute la partie du nombre multiple de 10Modèle:Exp. Modèle:Ancre

Divisibilité par DModèle:' 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

• Modèle:Ouvrage;
• Modèle:Article;
• Modèle:Article;
• Modèle:Ouvrage ;
• Modèle:Ouvrage.

Liens externes

• Modèle:Lien web
• Modèle:Article