Critère de divisibilité

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 » (voir la liste de critères de divisibilité), les critères de divisibilité sont basé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é[modifier | modifier le code]

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.

Exemple et démonstration de critères de divisibilité[modifier | modifier le code]

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 – 1a1a0, c'est-à-dire que a0 est le chiffre des unités, a1 est le chiffre des dizaines, etc. d'où

A = a0 + a1 × 10 + a2 × 102 + … + an × 10n.

De plus, on notera d le nombre de dizaines de A (à ne pas confondre avec chiffre des dizaines) :

d = anan – 1a1 = a1 + a2 × 10 + … + an × 10n – 1, ainsi : A = (d × 10) + a0.

Par 2[modifier | modifier le code]

Un nombre est 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[modifier | modifier le code]

Un nombre est divisible par 3 si et seulement si la somme de ses chiffres est divisible par 3.

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).

Par 7[modifier | modifier le code]

Énoncé 1[modifier | modifier le code]

Un nombre est divisible par 7 si et seulement si le résultat de la soustraction du nombre de dizaines par le double du chiffre des unités (soit : d – 2a0) est multiple de 7.

Exemple  :

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[modifier | modifier le code]

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.

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.

Démonstration pour un nombre quelconque[modifier | modifier le code]

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 × 5pm est premier avec 10 ;
  • d'après le lemme de Gauss, 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[modifier | modifier le code]

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[modifier | modifier le code]

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.

Divisibilité par m premier avec 10[modifier | modifier le code]

Ruban de Pascal[modifier | modifier le code]

Article détaillé : 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[modifier | modifier le code]

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[précision nécessaire] ce principe.

Exemple  :

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[Comment ?] au bout de n étapes si le nombre A est de l'ordre de 10n.

Réduction de la taille du nombre[modifier | modifier le code]

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  A=\sum_{i=0}^{n_r-1}A_i10^{ri}

  • 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 : A0A1 + A2 – ....

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

Exemple  :

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[modifier | modifier le code]

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[modifier | modifier le code]

André Deledicq, La jubilation en mathématiques, Paris, ACL – Les éditions du Kangourou,‎ 2005, 32 p. (ISBN 978-2-87694091-8)

Liens externes[modifier | modifier le code]