Critère de divisibilité

Un article de Wikipédia, l'encyclopédie libre.

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.

Sommaire

1 Recherche d'un critère de divisibilité
2 Exemple et démonstration de critères de divisibilité
3 Démonstration pour un nombre quelconque
4 Remarque sur la complexité algorithmique
5 Bibliographie
6 Voir aussi

[modifier] 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 7485 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.

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

Avant d'aborder la méthode générale, sont présentées ici quelques critères de divisibilité qui illustrent les techniques utilisées. Une liste très complète des critères de divisibilité figurent dans l'article liste de critères de divisibilité .

On aborde les démonstrations dans $\mathbb{N}$ 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 = \overline{a_n a_{n-1}...a_1 a_0}$ , c'est-à-dire que $a 0$ est le chiffre des unités, $a 1$ est le chiffre des dizaines, etc.

d'où $A = a_0 + a_1 \times 10 + a_2 \times 10^2 + ... + a_n \times 10^n$

Le symbole $\sum$ utilisé dans l'article est l'opérateur de l'addition, il se nomme sigma.

[modifier] par 2

[modifier] Énoncé

Un nombre est divisible par 2 si son chiffre des unités est 0;2;4;6;8.

[modifier] Démonstration

$A = 10B + a_0\,$

10B est toujours multiple de 2 donc A est multiple de 2 si et seulement si $a 0$ est multiple de 2.

[modifier] par 3

[modifier] Énoncé

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

[modifier] Démonstration

Soit A un entier naturel divisible par 3.

$3 | A \Leftrightarrow A \equiv 0 \pmod{3}$

$A = a_0 + a_1 \times 10 + a_2 \times 10^2 + ... + a_n \times 10^n$

$\mbox{Or, }10 \equiv 1 \pmod{3}$

$\mbox{Donc, }A \equiv 0 \pmod{3} \Leftrightarrow a_0 + a_1 + ... + a_n \equiv 0 \pmod{3}$

Conclusion : Lorsqu'un nombre est divisible par 3, la somme des chiffres de ce nombre est divisible par 3.

Remarque, par une démonstration analogue, on démontre aussi qu'un nombre est divisible par 9 si la somme de ses chiffres est divisible par 9. (puisque $10 \equiv 1 \pmod{9}$ )

[modifier] par 7

[modifier] Énoncé

Un nombre est divisible par 7 si le résultat de la soustraction du nombre de dizaines (à ne pas confondre avec chiffre des dizaines) par le double du chiffre des unités est divisible par 7.

[modifier] Démonstration

Soit A un entier naturel divisible par 7,

$A = a_0 + a_1 \times 10 + a_2 \times 10^2 + ... + a_n \times 10^n$

$7 \, | \, A \mbox{ et } 7 \, | \, 21 \mbox{ donc } 7 \, | \, A - 21a_0$

$7 \, | \, a_0 + a_1 \times 10 + a_2 \times 10^2 + ... + a_n \times 10^n - 21a_0$

$7 \, | \, a_1 \times 10 + a_2 \times 10^2 + ... + a_n \times 10^n - 20a_0$

$7 \, | \, 10(a_1 + a_2 \times 10 + ... + a_n \times 10^{n-1} - 2a_0)$

Or, 7 et 10 sont premiers entre eux, donc d'après le théorème de Gauss :

$7 \, | \, a_1 + a_2 \times 10 + ... + a_n \times 10^{n-1} - 2a_0$

Réciproquement, si $7 \, | \, a_1 + a_2 \times 10 + ... + a_n \times 10^{n-1} - 2a_0$

alors $7 \, | \, 10(a_1 + a_2 \times 10 + ... + a_n \times 10^{n-1} - 2a_0)$

Or, $7 \, | \, 21$ donc $7 \, | \, a_1 \times 10 + a_2 \times 10^2 + ... + a_n \times 10^n - 20 a_0 + 21 a_0$

On obtient : $7 \, | \, A$

Conclusion : $7 \, | \, A \Leftrightarrow 7 \, | \, (\overline{a_n a_{n-1}...a_1} - 2a_0)$

[modifier] Démonstration pour un nombre 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' \times 2^q\times 5^p$ où d' est premier avec 10
d divise A si et seulement si d' , $2 q$ et $5 p$ divisent A

[modifier] 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 2512 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

[modifier] 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:

9864375 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

[modifier] Divisibilité par d' premier avec 10

Puisque d' est premier avec 10, il existe un entier k tel que $10k \equiv 1 \pmod{d'}$ . C'est l'application de l'identité de Bézout. Alors le nombre A sera divisible par d' si et seulement si le nombre $B=\overline{a_n a_{n-1}...a_1 }+ ka_0$ est multiple de d'

Démonstration

$A=\overline{a_n a_{n-1}...a_1a_0 } = 10\times \overline{a_n a_{n-1}...a_1 }+ a_0$

$A \equiv 0 \pmod {d'} \Leftrightarrow 10\times \overline{a_n a_{n-1}...a_1 }+ a_0 \equiv 0 \pmod{d'}$

Comme k est premier avec d', on peut multiplier la congruence par k en conservant l'équivalence, et comme $10k \equiv 1 \pmod {d'}$ , on a

$A \equiv 0 \pmod {d'} \Leftrightarrow \overline{a_n a_{n-1}...a_1 }+ k.a_0 \equiv 0 \pmod{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 \equiv 1 \pmod {7}$ , et pour d' = 93, cet entier est 28 car $280 \equiv 1 \pmod {93}$

Ensuite, il suffit de réitérer autant que fois que nécessaire le principe précédent : pour vérifier, par exemple, que 111258 est divisible par 7

11258 est divisible par 7 si et seulement si 11125 - 2 × 8 , c’est-à-dire 11109, est divisible par 7

11109 est divisble par 7 si et seulement si 1110 - 18, c’est-à-dire 1092 l'est aussi

1092 est divisible par 7 si et seulement si 109 - 4, 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 n$ . On peut raccourcir ce travail pour les très grands nombres en cherchant le plus petit entier m tel que $10^m \equiv 1 \pmod {d'}$ . Cet entier existe dès que d' est premier. 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^6 \equiv 1 \pmod 7$ donc pour la divibilité par 7, on découpera en tranches de 6.

109 826304 est divisible par 7 si et seulement si 826304 + 109, c’est-à-dire 826413 l'est , si et seulement si 82641 - 6 (= 82635) l'est, si et seulement si 8263-10 (=8253) l'est, si et seulement si 825-6 (= 819) l'est, si et seulement si 81-18 (= 63) l'est.

[modifier] Remarque sur la complexité algorithmique

In fine, on peut trouver de cette manière pour chaque nombre d un critère de divisibilité par d. 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 d, il suffit de calculer la division euclidienne de A par d, 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 d 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 chiffre du nombre A initial. Pour un calcul à la main en base 10, du moins pour les petites diviseurs d, 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.

[modifier] Bibliographie

DELEDICQ, André. La jubilation en mathématiques. Paris : ACL — Les éditions du Kangourou, 2005. 32 pages. (ISBN 2876940914)

[modifier] Voir aussi

Portail des mathématiques

Critère de divisibilité

Un article de Wikipédia, l'encyclopédie libre.

Sommaire

[modifier] Recherche d'un critère de divisibilité