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 p en base 10, il suffit de chercher un multiple de p s'écrivant 10k +1, k étant entier.

Il suffit alors de retrancher k fois le chiffre des unités au nombre de dizaines. Par exemple, pour 7485 et p = 7, on a 748 - 2 × 5 = 738 et on réitère en partant de 738. Finalement 7485 sera multiple de 7 si et seulement si le nombre final est 7 (ou 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 – 1…a1a0, 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 – 1…a1 = 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 pair (ce qui comprend zéro).

En effet, A = 10d + a0 et 10d 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  :

273

nombre de dizaines : 27 ; chiffre des unités : 3

27 – 2 × 3 = 21 est divisible par 7, donc 273 l'est aussi.

Énoncé 2[modifier | modifier le code]

En utilisant la clé de divisibilité : 1, 3, 2, 6, 4, 5. Celle-ci s'obtient avec les restes de la division de 1, 10, 100, etc. par 7. Elle 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  :
  • Est-ce que 19 231 est divisible par 7 ?
    (1 × 1) + (3 × 3) + (2 × 2) + (9 × 6) + (1 × 4) = 1 + 9 + 4 + 54 + 4 = 72 n'est pas un multiple de 7
    donc 19 231 n'est pas divisible par 7.
  • Est-ce que 21 357 est divisible par 7 ?
    (7 × 1) + (5 × 3) + (3 × 2) + (1 × 6) + (2 × 4) = 7 + 15 + 6 + 6 + 8 = 42 est un multiple de 7
    donc 21 357 est divisible par 7.

Par 11[modifier | modifier le code]

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 n, on procède en plusieurs étapes :

  • on décompose n sous la forme d' × 2q × 5p où d' est premier avec 10 ;
  • n divise A si et seulement si d', 2q et 5p divisent A.

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 les 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 d' premier avec 10[modifier | modifier le code]

Puisque d' est premier avec 10, il existe un entier k tel que 10 × k ≡ 1 mod d'. C'est l'application du théorème de Bachet-Bézout. Alors le nombre A sera divisible par d' si et seulement si le nombre d + (k × a0) est multiple de d', 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 que fois que nécessaire ce principe.

Exemple  :

La première difficulté est de trouver cet entier k (le plus proche de 0 possible). Par exemple, pour d' = 7, cet entier est –2 car –20 ≡ 1 mod 7 (pour d' = 93, cet entier serait 28 car 280 ≡ 1 mod 93).

Ensuite, pour vérifier, par exemple, que 111 258 est divisible par 7 :

111 258 est divisible par 7 si et seulement si 11 125 – 2 × 8, c’est-à-dire 11 109, est divisible par 7 ;

11 109 est divisible par 7 si et seulement si 1 110 – 2 × 9, c’est-à-dire 1 092, l'est aussi ;

1 092 est divisible par 7 si et seulement si 109 – 2 × 2, c’est-à-dire 105, est divisible par 7 ;

enfin 105 est divisible par 7 car 10 – 2 × 5, c’est-à-dire 0, est divisible par 7.

Cette méthode a l'avantage de se terminer au bout de n étapes si le nombre est de l'ordre de 10n. 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 m tel que 10m ≡ 1 mod d'. Cet entier existe dès que d' est premier avec 10. On découpe alors le nombre A par tranches de m chiffres, on ajoute entre eux les nombres issus de ce découpage, on obtient ainsi un nombre B dont l'ordre de grandeur est voisin de 10m. A sera divisible par d' si et seulement si B l'est.

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, si et seulement si 82 641 – 2 × 3 = 82 635 l'est, si et seulement si 8 263 – 2 × 5 = 8 253 l'est, si et seulement si 825 – 2 × 3 = 819 l'est, si et seulement si 81 – 2 × 9 = 63 l'est. Donc il l'est.

Remarque sur la complexité algorithmique[modifier | modifier le code]

In fine, on peut trouver de cette manière, pour tout n, un critère de divisibilité par n. Il faut d'abord remarquer qu'un critère général itératif existe : un nombre A est divisible par n, si le reste de la division euclidienne de A par n 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 n 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 10, du moins pour les petits diviseurs n, 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 2876940914)