Voir la source de 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 naturel|entier]] permettant de déterminer si ce nombre est [[divisibilité|divisible]] par un autre. Malgré leur apparence de « recette de cuisine », les critères de divisibilité sont fondés sur des [[démonstration (logique et mathématique)|démonstrations]] mathématiques ; il est possible d'en trouver pour n'importe quel nombre grâce aux [[Congruence sur les entiers|congruences]].
{{Voir|Liste de critères de divisibilité}}

== 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]]'' ({{s-|VI}}), l'utilisation de la propriété suivante<ref name=McDowellBeginnings>{{article|langue=en|auteur=Eric L. McDowel|titre=Divisibility Tests: A History and User's Guide - The Beginnings of Divisibility|périodique=Convergence|éditeur=Mathematical association of america|mois=mai|année=2018|lire en ligne=https://maa.org/press/periodicals/convergence/divisibility-tests-a-history-and-users-guide-the-beginnings-of-divisibility}}</ref> :
: <math> 100c+u</math> et <math> 2c+u</math> ont même reste dans la division par 7;

Selon Fontés{{sfn|Fontés|1893|p=461}}, 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{{sfn|Fontés|1893|p=462}}.

[[Blaise Pascal]], dans son ''De Numeris Multiplicibus''<ref> Voir sur [[s:Page:Œuvres de Blaise Pascal, III.djvu/327|wikisource]]</ref> 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<ref>{{article|prénom1=Georg Wolfgang|nom1=Krafft|langue=la|titre=Observationes arithmeticae de septenario|périodique=
Commentarii Academiae scientiarum imperialis Petropolitanae|volume=VI|passage=41-45|année=1738|lire en ligne=https://www.biodiversitylibrary.org/item/38582#page/51/mode/1up}}</ref> des critères de divisibilité par 7 et propose à cette occasion  une méthode de réduction par la droite{{sfn|Krafft|1738|p=45}}: il remarque que, si <math>10c+b=3m</math>, alors le nombre <math>N</math> égal à <math>10a + b</math> est divisible par 7 si et seulement si <math>a + m - c</math> est divisible par 7.

En 1795, [[Joseph-Louis Lagrange]]<ref>{{chapitre|auteur=Joseph-Louis Lagrange|titre=Lecons élémentaires sur les mathématiques données à l'École Normale en 1795|titre ouvrage=Œuvres de lagrange publiées par less soins de M. J.-A. Serret|tome=7|passage=204-208|lire en ligne=https://gallica.bnf.fr/ark:/12148/bpt6k2299428/f206.item |année=1795}}</ref> 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{{sfn|Lagrange|1795|p=206}}, de telle sorte que les coefficients soient, en [[valeur absolue]], plus petits que D/2{{sfn|Dickson|1919|p=338}}.

Le {{s-|XIX}} voit fleurir de nombreuses publications sur les critères de divisibilité par réduction par la droite. En 1834, {{lien|langue=sv|trad=Carl Johan Hill}} présente, sans démonstration et en se référant à Krafft<ref>{{article|langue=la|prénom=Carl Johan|nom= Hill|titre=De factoribus numerorum compositorum dignoscendis|périodique=[[Journal für die reine und angewandte Mathematik]]|année=1834|lire en ligne=https://gdz.sub.uni-goettingen.de/id/PPN243919689_0011 |passage=251-261}}</ref>, de multiples critères de réduction par la gauche{{sfn|Hill|1834|p=252-253}} (divisibilité par 13, 17, 59, 73, 97, 103, 137, ...) ou par la droite{{sfn|Hill|1834|p=254-255}} (divisibilité par 7, 11, 29,...) par tranches de un, deux ou trois chiffres. En 1844, [[August Leopold Crelle]] publie dans son ''[[Journal für die reine und angewandte Mathematik|Journal]]''<ref>{{article|langue=de|prénom1=August Leopold|nom1=Crelle|titre=Encyklopädische une elemantare Darstellung des Theorie der Zahlen|périodique=[[Journal für die reine und angewandte Mathematik]]|année=1844|lire en ligne=https://www.digizeitschriften.de/id/243919689_0027 |passage=107-181}}</ref> 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{{sfn|Crelle|1844|p=125}}:
{{retrait|pour un nombre <math> Z=x_mA^m + x_{m-1}A^{m-1} + \cdots + x_1A + x_0</math>, et pour un diviseur <math> s</math>, si les entiers <math> n</math> et <math> r</math> sont liés par la relation <math>nA=r+ks</math> alors, en posant <math> z = x_mr^m+x_{m-1}r^{n-1}n + \cdots +x_1r^{1}n^{m-1}+x_0n^m</math>, on a <math>Z</math> est divisible par <math> s</math> si et seulement si <math>z</math> l'est.}}
Le cas <math>n=\pm 1</math> donne un critère de réduction par la gauche et le cas <math>r=\pm 1</math>  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<ref>{{article|auteur=A. Zbikowski|titre=Note sur la divisbilité des nombres|périodique=Bulletin de l'académie Impériale des Sciences de Saint-petersbourg|année=1961|passage=151-153|lire en ligne=https://www.biodiversitylibrary.org/page/33837551}}</ref> 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<ref name=Loir>{{article|auteur=M. Loir|titre=Caractère de divisibilité d'un nombre par un nombre premier quelconque|périodique=Comptes rendus hebdomadaires des séances de l'académie des sciences|mois=janvier|année=1888|lire en ligne=https://gallica.bnf.fr/ark:/12148/bpt6k3062v/f1070.vertical |passage=1070-1071|tome=CVI|numéro=15}}</ref>.

== Notations ==
Par la suite, on notera <math> A=\overline{a_na_{n-1}\cdots a_1a_0}=\sum_{k=0}^na_k10^k=10d+a_0</math>, le nombre dont la  divisibilité par <math>D </math> est étudiée.

== Méthode de Pascal ==
{{article détaillé|Ruban de Pascal}}
On calcule à l'avance le reste de chaque puissance de 10 dans la division par <math>D</math> (on le diminue éventuellement{{sfn|Humbert|1893|p=104}} de <math>D</math> s'il dépasse <math>D/2</math>). Il n'y a qu'un nombre fini de restes à calculer car ce  « ruban » de restes est [[Suite périodique|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{{sfn|Humbert|1893|p=104}}. 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 <math>A</math> dans la division par <math>D</math>.

Cette méthode fournit non seulement un critère de divisibilité mais donne également un moyen de connaitre le reste de la division de <math>A</math> par <math>D</math>.

Elle se généralise à l'écriture de <math> A</math> dans toute base{{sfn|Humbert|1893|p=106}} <math> B</math> en cherchant les restes des puissances de <math> B</math> dans la division par <math> D</math> 
=== 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 : 
{{retrait|Un nombre est pair, c'est-à-dire divisible par 2, si et seulement si{{sfn|Humbert|1893|p=93}} 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 
{{retrait|Un nombre est divisible par 3 si et seulement si{{sfn|Humbert|1893|p=95}} 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 : 
{{retrait|Un nombre est  divisible par 5, si et seulement si{{sfn|Humbert|1893|p=93}} 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 
{{retrait|Un nombre est divisible par 9 si et seulement si{{sfn|Humbert|1893|p=95}} 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
{{retrait|Un nombre est divisible par 11 si et seulement si{{sfn|Humbert|1893|p=96}}  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 [[Ruban de Pascal|clé de divisibilité]] : 1, 3, 2, −1, −3, −2. Celle-ci s'obtient par exemple à partir des restes de la division{{sfn|Humbert|1893|p=103}} 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.
{{retrait|Un nombre est divisible par 7 si et seulement si{{sfn|Humbert|1893|p=103}} le nombre obtenu à l'issue de cette somme-produit est divisible par 7}}

{{exemple|nom=Exemples|
*Pour vérifier, par exemple, que {{nombre|826413}} 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, {{nombre|19231}} 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ù <math>D</math> 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{{exp|''r''}} ≡ ±1 mod ''D'' (pour 10{{exp|''r''}} ≡ +1 mod ''D'', cet entier ''r'' est la période du [[#Ruban de Pascal|ruban de Pascal en base dix]]), puis on applique la méthode du « ruban de Pascal en base 10{{exp|''r''}} », base pour laquelle la clé de divisibilité est très simple :

L'entier ''A'' peut se découper en ''n''{{ind|''r''}} blocs de ''r'' chiffres
{{retrait|<math> A=\sum_{i=0}^{n_r-1}A_i10^{ri}</math>}}
ceci correspond à l'écriture de ''A'' dans la base <math> 10^r</math>. Et l'on applique alors la méthode de Pascal.
* si 10{{exp|''r''}} est congru à 1 modulo ''D'', l'entier ''A''  a même reste que la somme de ces ''n''{{ind|''r''}} blocs.
* si 10{{exp|''r''}} est congru à –1 modulo ''D'', l'entier ''A'' a même reste que la somme alternée de ces ''n''{{ind|''r''}} blocs : {{formule|''A''{{ind|0}} – ''A''{{ind|1}} + ''A''{{ind|2}} –  ...}}.

On obtient ainsi un nombre ''B'' dont l'ordre de grandeur est voisin de 10{{exp|''r''}}.

{{exemple|
10{{exp|6}} ≡ 1 mod 7 donc pour la divisibilité par 7, on découpera en tranches de 6. 

{{nombre|1000109826303}} est divisible par 7 si et seulement si {{nombre|826303}} + 109 + 1, c'est-à-dire {{nombre|826413}}, l'est. Une fois le nombre ainsi réduit, [[#Élimination des unités|l'une]] ou [[#Énoncé 2|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{{exp|3}} ≡ –1 mod 7 et que l'on peut faire la somme alternée des blocs de 3 chiffres :

{{nombre|1000109826303}} 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 <math>A</math>, 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 <math>D</math> 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 <math>D</math> est premier avec 10, il existe deux entiers naturels <math>\alpha</math> (<math>\alpha <10 </math>) et  <math>\beta</math> tels que <math>\alpha D - \beta 10=1</math> (d'après le [[Théorème de Bézout]]).

Pour <math>A=10d+a_0</math>, on pose <math> A'=d-\beta a_0</math>. <math>A</math> est divisible par <math>D</math> si et seulement si <math>A'</math> l'est aussi<ref name=Loir/>
{{démonstration|déroulante=oui|contenu=
<math> 10A'=10d-10\beta a_0=10d+a_0-\alpha Da_0=A -\alpha Da_0 </math>

Donc <math>A</math> est multiple de <math>D</math> si seulement si <math>10A'</math> est multiple de <math>D</math>. Comme 10 est premier avec <math>D</math>, <math>10A'</math> est multiple de <math>D</math> si et seulement si  <math>A'</math> est multiple de <math>D</math>}}

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

{{exemple|
Pour la divisibilité par 7, on peut remarquer que <math>3 \times 7 - 2\times 10 = 1</math> ce qui fournit <math>\alpha=3</math> et <math>\beta=2</math>.

Ensuite, pour vérifier, par exemple, que {{nombre|826413}} est divisible par 7 :

{{nombre|826413}} est divisible par 7 si et seulement si {{nombre|82641}}  – 2 × 3, c'est-à-dire {{nombre|82635}}, l'est ;

{{nombre|82635}} est divisible par 7 si et seulement si {{nombre|8263}}  – 2 × 5, c'est-à-dire {{nombre|8253}}, l'est ;

{{nombre|8253}} 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 <math>D</math> qui se termine par 1. L'observation du chiffre des unités de <math> D</math> permet de distinguer 4 cas<ref name=Loir/>:
* <math>D=10m+1 \quad \alpha=1 \quad \beta=m</math>
* <math>D=10m+3 \quad \alpha=7 \quad 7D=10\times 7m+20+1 \quad \beta=7m+2</math>
* <math>D=10m+7 \quad \alpha=3 \quad 3D=10\times 3m+20+1 \quad \beta=3m+2</math>
* <math>D=10m+9 \quad \alpha=9 \quad 9D=10\times 9m+80+1 \quad \beta=9m+8</math>

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 <math>A_0=A ,\, A_1=|A'_0|,\cdots,\, A_{n+1}=|A'_n|, \cdots</math>  La suite est décroissante tant que <math>A_n\ge \alpha D</math>
{{démonstration|déroulante=oui|contenu=
On sait que <math> A'_n=\frac{A_n-\alpha Da_0}{10}</math> (voir démonstration précédente). Donc <math>A'_n  < A_n</math>
* Si <math>A'_n \ge 0</math>, on a bien <math> A_{n+1} < A_n</math> 
* Si <math>A'_n < 0</math>, on a <math> A_{n+1} = - A'_n =\frac{\alpha Da_0 - A_n}{10} \le \frac{A_na_0 - A_n}{10}</math>. Or <math>\frac{A_na_0 - A_n}{10}=\frac{a_0-1}{10} A_n < A_n </math>. Donc <math> A_{n+1} < A_n</math>
}}

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

{{Exemple|numéro=1|
On cherche la divisibilité de {{nombre|24213}} par 33. On sait que <math> \alpha=7 </math> et <math>\beta=23</math> 
:<math>A_1=2421-3\times 23= 2352</math>
:<math>A_2=242-5\times 23 = 189</math>
:<math>A_3=|18-9\times 23| = 189</math>
La suite cesse d'être décroissante, <math> 6\times 33=198</math> et <math> 5\times 33=165</math> donc 189 n'est pas multiple de 33 et {{nombre|24213}} non plus.}}
{{Exemple|numéro=2|On cherche la divisibilité de {{nombre|17603}} par 29.  On sait que <math> \alpha=9 </math> et <math>\beta=26</math> 
:<math>A_1=1760-3\times 26= 1682</math>
:<math>A_2=168-2\times 26 = 116</math>
:<math>A_3=|11-6\times 26| = 145</math>
La suite cesse d'être décroissante, <math> 4\times 29=116</math> donc {{nombre|17603}} est divisible par 29}}

=== Méthode additive ===
==== Critère ====
Puisque <math>D</math> est premier avec 10, il existe deux entiers naturels <math>\alpha</math> (<math>\alpha <10 </math>) et  <math>\beta</math> tels que <math>\alpha D - \beta 10=-1</math>. Soit encore <math>\alpha D= (\beta- 1)10+9</math>

Pour <math>A=10d+a_0</math>, on pose <math> A'=d+\beta a_0</math>. <math>A</math> est divisible par <math>D</math> si et seulement si <math>A'</math> l'est aussi<ref name=McDowellZbikowski>{{article|langue=en|auteur=Eric L. McDowel|titre=Divisibility Tests: A History and User's Guide - Zbikowski Divisibility Tests|périodique=Convergence|éditeur=Mathematical association of america|mois=mai|année=2018|lire en ligne=https://maa.org/press/periodicals/convergence/divisibility-tests-a-history-and-users-guide-zbikowski-divisibility-tests}} - Addition style Zbikowski tests</ref>.
{{démonstration|déroulante=oui|contenu=
<math> 10A'=10d+10\beta a_0=10d+a_0+\alpha Da_0= A +\alpha Da_0 </math>

Donc <math>A</math> est multiple de <math>D</math> si seulement si <math>10A'</math> est multiple de <math>D</math>. Comme 10 est premier avec <math>D</math>, <math>10A'</math> est multiple de <math>D</math> si et seulement si  <math>A'</math> est multiple de <math>D</math>}}

En général, cette technique permet de diminuer la taille du nombre et peut se réitérer avec le nombre <math>A'</math> jusqu'à reconnaitre un multiple ou un non-multiple de <math>D</math>.
{{exemple|
Pour la divisibilité par 19, on peut remarquer que <math>19 = 1\times 10 + 9</math> ce qui fournit <math>\alpha=1</math> et <math>\beta=2</math>.

Ensuite, pour vérifier, par exemple, que {{nombre|2508}} est divisible par 19 :

{{nombre|2508}} 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 {{nombre|2508}} est divisible par 19
}}

==== Recherche des coefficients ====
Il s'agit de trouver le plus petit multiple de <math>D</math> qui se termine par 9. L'observation du chiffre des unités de <math> D</math> permet de distinguer 4 cas<ref>Suite [http://oeis.org/A333448 A333448] dans [[OEIS]]</ref>:
* <math>D=10m+1 \quad \alpha=9 \quad \beta=9m</math>
* <math>D=10m+3 \quad \alpha=3 \quad 3D=10\times 3m+9 \quad \beta=3m+1</math>
* <math>D=10m+7 \quad \alpha=7 \quad 3D=10\times 7m+40+9 \quad \beta=7m+5</math>
* <math>D=10m+9 \quad \alpha=1 \quad \beta=m+1</math>

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 <math>A_0=A ,\, A_1=A'_0,\cdots,\, A_{n+1}=A'_n, \cdots</math>  La suite est décroissante tant que <math>A_n> \alpha D</math>
{{démonstration|déroulante=oui|contenu=
On sait que <math> A'_n=\frac{A_n+\alpha Da_0}{10}</math> (voir démonstration précédente). Donc 

Puisque <math> A_n > \alpha D</math>, on a <math> A_{n+1} \le \frac{A_n+A_na_0}{10}\le A_n</math>. Donc <math> A_{n+1} < A_n</math>
}}

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

{{Exemple|numéro=1|
On cherche la divisibilité de {{nombre|3136}} par 7. On sait que <math> \alpha=7 </math> et <math>\beta=5</math> 
:<math>A_1=313+6\times 5= 343</math>
:<math>A_2=34+3\times 5 = 49</math>
:<math>A_3=4 + 9\times 5 = 49</math>
La suite cesse d'être décroissante, <math> 7\times 7 = 49</math> donc {{nombre|3136}} est divisible par 7.}}
{{Exemple|numéro=2|On cherche la divisibilité de {{nombre|27603}} par 29.  On sait que <math> \alpha=1 </math> et <math>\beta=3</math> 
:<math>A_1=2760+3\times 3= 2769</math>
:<math>A_2=276+9\times 3 = 303</math>
:<math>A_3=30+3\times 3 = 39</math>
:<math>A_4=3+9\times 3 = 30</math> qui n'est pas multiple de 29 donc {{nombre|27603}} 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{{exp|''q''}} × 5{{exp|''p''}} où  ''D{{'}}''  est [[premier avec]] 10 ;
* à la suite de la transitivité de la division euclidienne et par conséquent du [[Lemme d'Euclide|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{{exp|''q''}} et 5{{exp|''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{{exp|''q''}} ===
''A'' est divisible par 2{{exp|''q''}} si et seulement si le nombre formé par les ''q'' premiers chiffres (en partant de l'unité) est divisible par 2{{exp|''q''}}.
 
''Exemple'' : {{nombre|79532512}} est divisible par 16 (= 2{{4}}) car {{nombre|2512}} est divisible par 16.

''Démonstration'' : 10{{exp|''q''}} est multiple de 2{{exp|''q''}}, donc on peut se débarrasser de toute la partie du nombre multiple de 10{{exp|''q''}}.

=== Divisibilité par 5{{exp|''p''}} ===
''A'' est divisible par 5{{exp|''p''}} si et seulement si le nombre formé par ses ''p'' premiers chiffres (en partant de l'unité) est divisible par 5{{exp|''p''}}.
 
''Exemple'' : {{nombre|9864375}} est divisible par 125 (= 5{{3}}) car 375 est divisible par 125.

''Démonstration'' : 10{{exp|''p''}} est multiple de 5{{exp|''p''}}, donc on peut se débarrasser de toute la partie du nombre multiple de 10{{exp|''p''}}.
{{Ancre|Divisibilité par d' premier avec 10}}
=== 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 [[Théorie de la complexité (informatique théorique)|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 [[poser une division|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 ==
* {{Ouvrage|langue=en|lien auteur=Leonard Eugene Dickson|prénom=Leonard Eugene|nom=Dickson|titre={{Lien|History of the Theory of Numbers}}|volume=1 |chapitre=Criteria for divisibility by a given number. |numéro chapitre=XII|référence=Référence:Histoire de la théorie des nombres (Dickson) |passage=337-346|année=1919 |url=https://archive.org/stream/historyoftheoryo01dick#page/336/mode/2up}};
* {{article|langue=en|auteur=Eric L. McDowel|titre=Divisibility Tests: A History and User's Guide|périodique=Convergence|éditeur=Mathematical association of america|mois=mai|année=2018|doi= 10.4169/convergence20180513|lire en ligne=https://maa.org/press/periodicals/convergence/divisibility-tests-a-history-and-users-guide}};
* {{article|auteur=M. Fontés|titre=Bilan des Caractères de divisibilité|date=1893|périodique=Mémoires de l'Académie des sciences, inscription et belles lettres (Toulouse)|numéro=9|tome=5|passage=459-465|lire en ligne=https://gallica.bnf.fr/ark:/12148/bpt6k57203023/f487.vertical}};
* {{ouvrage|auteur=[[Martin Gardner]]|titre=Le paradoxe du pendu et autres divertissements mathématiques |titre original=The Unexpected Hanging  & Other Mathematical Diversions |éditeur=Dunod |année=1971 |lieu=Paris |chapitre=Caractères de divisibilité |numéro chapitre=14 |passage=156-165}} ;
* {{ouvrage|auteur=Eugène Humbert |titre=Traité d'arithmétique |sous-titre=à l'usage des élèves de mathématiques élémentaires … |préface=[[Jules Tannery]] |éditeur=Librairie Nony |année=1893 |chapitre=Divisibilité |numéro chapitre=VI |passage=92-108|url=https://books.google.fr/books?id=Hc4GAAAAYAAJ}}.

== Références ==
{{Références}}

== Liens externes ==
*{{Lien web|langue=en|titre=Divisibility Tests Unified: Stacking the Trimmings for Sums|auteur=Edwin O'Shea|mois=6|année=2014|url=http://educ.jmu.edu/~osheaem/research/div-test-14-06.pdf}}
*{{Article|langue=en|titre=Stupid Divisibility Tricks — 101 Ways to Stupefy Your Friends|revue={{Lien|Math Horizons}}|vol=14|numéro=2|année=2006|auteur=Marc Renault|url=http://webspace.ship.edu/msrenault/divisibility/StupidDivisibilityTricks.pdf|p.=18-21, 42}}

{{Portail|arithmétique}}

[[Catégorie:Divisibilité et factorisation]]
[[Catégorie:Algorithmique]]