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.
Recherche d'un critère de divisibilité
Pour chercher un critère de divisibilité par m en base 10, il suffit de chercher s'il existe un entier relatif k tel que 10k – 1 soit un multiple de m (on scrute donc les nombres de la forme +…9 ou –…1).
Il suffit alors d'ajouter k fois le chiffre des unités au nombre de dizaines. Par exemple pour m = 7, l'entier k = –2 convient car 10k – 1 = –21 = –3m. Pour tester la divisibilité de 7 485, on calcule 748 + (–2) × 5 = 738 et l'on réitère en partant de 738. De proche en proche, 7 485 sera multiple de 7 si et seulement si le nombre final est un multiple de 7 (voir démonstration plus bas).
Exemples :
- 3 × 3 = 9 = 1 × 10 – 1 : on ajoutera les unités aux dizaines pour la divisibilité par 3 ou 9.
- –3 × 7 = –2 × 10 – 1 : on retranchera 2 fois les unités aux dizaines pour la divisibilité par 7 ou 3.
- –11 = –1 × 10 – 1 : on retranchera les unités aux dizaines pour la divisibilité par 11.
- 13 × 3 = 4 × 10 – 1 : on ajoutera 4 fois les unités aux dizaines pour la divisibilité par 13 ou 3.
- –17 × 3 = –5 × 10 – 1 : on retranchera 5 fois les unités aux dizaines pour la divisibilité par 17 ou 3.
- 29 = 3 × 10 – 1 : on ajoutera 3 fois les unités aux dizaines pour la divisibilité par 29.
- –31 = –3 × 10 – 1 : on retranchera 3 fois les unités aux dizaines pour la divisibilité par 31.
- –41 = –4 × 10 – 1 : on retranchera 4 fois les unités aux dizaines pour la divisibilité par 41.
Remarque :
- Si 10k – 1 est multiple de m alors 10(k ± m) – 1 aussi. Par exemple pour m = 7, on a choisi ci-dessus k = –2 (la solution la plus proche de 0) mais on pourrait tout aussi bien choisir, par exemple, k = –2 + 7 = 5 (la plus petite solution positive).
Exemple et démonstration de critères de divisibilité
Avant d'aborder la méthode générale, sont présentés ici quelques critères de divisibilité qui illustrent les techniques utilisées. Une liste plus fournie de critères figure dans l'article liste de critères de divisibilité.
On aborde les démonstrations dans ℕ car un entier relatif a les mêmes diviseurs que sa valeur absolue.
Ci-dessous sont expliquées les notations utilisées dans le reste de l'article.
Soit A un entier naturel. On pose A = anan – 1…a1a0, c'est-à-dire que a0 est le chiffre des unités, a1 est le chiffre des dizaines, etc. d'où
De plus, on notera d le nombre de dizaines de A (à ne pas confondre avec chiffre des dizaines) :
Par 2
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.
En effet, A = (d × 10) + a0 et d × 10 est toujours multiple de 2, donc A est multiple de 2 si et seulement si a0 est multiple de 2.
Par 3
Un nombre est divisible par 3 si et seulement si la somme de ses chiffres est divisible par 3 (la sommation des chiffres peut s'appliquer à nouveau à la somme obtenue et ainsi de suite jusqu'à obtenir 3, 6, ou 9).
On démontre de même qu'un nombre est divisible par 9 si et seulement si la somme de ses chiffres est divisible par 9 (puisque 10 est congru à 1 non seulement modulo 3, mais même modulo 9).
Énoncé 1
Un nombre est divisible par 7 si et seulement si la différence entre son nombre de dizaines et le double de son chiffre des unités (soit : d – 2a0) l'est.
413
nombre de dizaines : 41 ; chiffre des unités : 3
41 – 2 × 3 = 35 est divisible par 7, donc 413 l'est aussi.
Énoncé 2
En utilisant 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. Cette méthode est aussi valable pour tous les autres diviseurs.
On multiplie par le chiffre correspondant de la clé chaque chiffre du nombre à analyser en commençant par les unités.
- 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.
Démonstration pour un nombre quelconque
De manière générale, pour déterminer si un nombre A est divisible par M, on procède en plusieurs étapes :
- on décompose M sous la forme m × 2q × 5p où m 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), M divise A si et seulement si m, 2q et 5p divisent A ;
- optionnellement, si l'on dispose d'une factorisation de m en produit de facteurs deux à deux premiers entre eux, on peut de même réduire le problème de la divisibilité par m 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.
Ruban de Pascal
L'énoncé 2 ci-dessus se généralise (voir l'article détaillé pour plus d'exemples) : on calcule à l'avance le reste de chaque puissance de 10 dans la division par m (on le diminue éventuellement de m s'il dépasse m/2). Comme m est premier avec 10, il n'y a qu'un nombre fini de restes à calculer car ce « ruban » de restes est périodique : on le constate dès qu'on retrouve 1 comme reste, ce que le théorème d'Euler permettait de prévoir. 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 m.
Élimination des unités
Cette méthode permet de ne faire toujours qu'un seul type d'opération.
Puisque m est premier avec 10, il existe un entier k tel que 10 × k ≡ 1 mod m. C'est l'application du théorème de Bachet-Bézout. Alors le nombre A sera divisible par m si et seulement si le nombre |d + (k × a0)| est multiple de m, où d désigne, comme ci-dessus, le nombre de dizaines de A et a0 son chiffre des unités. Ensuite, il suffit de réitérer autant de fois que nécessaire ce principe.
La première difficulté est de trouver cet entier k (le plus proche de 0 possible). Par exemple, pour m = 7, cet entier est –2 car –20 ≡ 1 mod 7 (pour m = 93, cet entier serait 28 car 280 ≡ 1 mod 93).
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.
Cette méthode a l'avantage de se terminer au bout de n étapes si le nombre A est de l'ordre de 10n.
Réduction de la taille du nombre
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 m (pour 10r ≡ +1 mod m, 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
- si 10r est congru à 1 modulo m, l'entier A a même reste que la somme de ces nr blocs.
- si 10r est congru à –1 modulo m, 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. L'une ou l'autre des deux méthodes précédentes montre que 413 est divisible par 7.
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
- André Deledicq, La jubilation en mathématiques, Paris, ACL – Les éditions du Kangourou, , 32 p. (ISBN 978-2-87694091-8, présentation en ligne), « Un critère de divisibilité par 7 » ;
- (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;
- 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.
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)