Critère de divisibilité

Cet article est une ébauche concernant les mathématiques. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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é

Pour chercher un critère de divisibilité du nombre p en base 10, il suffit de chercher un multiple de p ayant une différence de 1 avec un multiple de 10, noté 10k.

Il suffit alors de multiplier le chiffre des unités par cet entier k et de l'ôter du nombre de dizaines. Par exemple, pour 7 485 et la divisibilité par 7, on retranche 2 × 5 à 748 et on recommence avec le résultat ainsi formé. Le nombre initial sera un multiple de p si et seulement si le nombre final est un multiple de p (voir démonstration plus bas)

Exemples :

• 3 × 3 = 9 = 1 × 10 – 1 donc il faudra ajouter les chiffres pour la divisibilité par 3 et par 9
• 3 × 7 = 2 × 10 + 1 donc il faudra retrancher les doubles des chiffres pour la divisibilité par 7 (et par 3)
• 11 = 1 × 10 + 1 donc il faudra retrancher les chiffres pour la divisibilité par 11
• 13 × 3 = 4 × 10 – 1 donc il faudra ajouter les quadruples des chiffres pour la divisibilité par 13 (et par 3)
• 17 × 3 = 5 × 10 + 1 donc il faudra retrancher les quintuples des chiffres pour la divisibilité par 17 (et par 3)
• 29 = 3 × 10 – 1 donc il faudra ajouter les triples des chiffres pour la divisibilité par 29
• 31 = 3 × 10 + 1 donc il faudra retrancher les triples des chiffres pour la divisibilité par 31
• 41 = 4 × 10 + 1 donc il faudra retrancher les quadruples des chiffres pour la divisibilité par 41
• etc.

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 = a_na_{n – 1}…a₁a₀, c'est-à-dire que a₀ est le chiffre des unités, a₁ est le chiffre des dizaines, etc. d'où

A = a₀ + a₁ × 10 + a₂ × 10² + … + a_n × 10ⁿ.

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

d = a_na_{n – 1}…a₁ = a₁ + a₂ × 10 + … + a_n × 10^{n – 1}, ainsi : A = (d × 10) + a₀.

Par 2

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) + a₀ et d × 10 est toujours multiple de 2, donc A est multiple de 2 si et seulement si a₀ 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.

Démonstration —

A est divisible par 3 si et seulement s'il est congru à 0 modulo 3. Or

A = a₀ + a₁ × 10 + a₂ × 10² + … + a_n × 10ⁿ.

Mais 10 est congru à 1 modulo 3, donc ses puissances aussi, donc

A ≡ a₀ + a₁ + a₂ + … + a_n mod 3.

Remarque : 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

Énoncé 1

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

Exemple  :

273

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

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

Démonstration —

A = (d × 10) + a₀. Posons B = d – (2 × a₀) et montrons (en utilisant que 21 est multiple de 7), que A est divisible par 7 si et seulement si B l'est.

A = (10 × B) + (21 × a₀) donc si B est divisible par 7 alors A aussi.

B = (–2 × A) + (21 × d) donc si A est divisible par 7 alors B aussi.

Énoncé 2

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.

Démonstration pour un nombre quelconque

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' × 2^q × 5^p où d' est premier avec 10 ;
• n divise A si et seulement si d', 2^q et 5^p divisent A.

Divisibilité par 2^q

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

Exemple : 79 532 512 est divisible par 16 (= 2⁴) car 2 512 est divisible par 16.

Démonstration : 10^q est multiple de 2^q, donc on peut se débarrasser de toute la partie du nombre multiple de 10^q.

Divisibilité par 5^p

A est divisible par 5^p si et seulement si le nombre formé par les p premiers chiffres (en partant de l'unité) est divisible par 5^p.

Exemple : 9 864 375 est divisible par 125 (= 5³) car 375 est divisible par 125.

Démonstration : 10^p est multiple de 5^p, donc on peut se débarrasser de toute la partie du nombre multiple de 10^p.

Divisibilité par d' premier avec 10

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 × a₀) est multiple de d', où d désigne, comme ci-dessus, le nombre de dizaines de A et a₀ son chiffre des unités. Ensuite, il suffit de réitérer autant que fois que nécessaire ce principe.

Démonstration —

A = (d × 10) + a₀ donc A est divisible par d' si et seulement si (d × 10) + a₀ ≡ 0 mod d'.

Comme k est premier avec d', on peut multiplier la congruence par k en conservant l'équivalence, et comme 10 × k ≡ 1 mod d', on a :

A est divisible par d' si et seulement si d + (k × a₀) ≡ 0 mod d'.

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 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 m tel que 10^m ≡ 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 10^m. A sera divisible par d' si et seulement si B l'est.

Exemple  :

10⁶ ≡ 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

In fine, on peut trouver de cette manière pour chaque nombre n un critère de divisibilité par n. Il faut d'abord remarquer qu'un critère général, manipulable algorithmiquement, préexiste : pour savoir si un nombre A est divisible par n, il suffit de calculer la division euclidienne de A par n, et de tester l'annulation du reste. Un tel calcul s'effectue en un nombre d'opérations contrôlé par le nombre de chiffres de A (complexité linéaire).

Les algorithmes présentés ici sont en fait précisément des variantes de cet algorithme général : on a vu en effet qu'on les obtient via un calcul modulaire, qui repose sur la notion de division euclidienne. Leur complexité est à nouveau linéaire : en effet, à 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 sera encore de l'ordre du nombre de chiffres du nombre A initial. Pour un calcul à la main en base 10, du moins pour les petites diviseurs n, ces méthodes ont un avantage, par rapport à la méthode générale par division euclidienne : on évite les calculs intermédiaires de division.

Il faut toutefois noter que ces méthodes ne fournissent qu'un critère de divisibilité, alors que la méthode générale est plus précise et fournit quotient et reste.

Bibliographie

André Deledicq, La jubilation en mathématiques, Paris, ACL – Les éditions du Kangourou, 2005, 32 p. (ISBN 2876940914)