Critère de divisibilité

En mathématiques et plus exactement en arithmétique modulaire, un critère de divisibilité est une particularité d'un entier servant à déterminer si ce nombre est divisible par un autre.

Catégories :

Divisibilité et factorisation - Arithmétique élémentaire - Mathématiques élémentaires - Algorithme

Page(s) en rapport avec ce sujet :

Un critère de divisibilité est une règle qui permet, sans effectuer la division, de savoir si un nombre est divisible ou non par un nombre donné.... (source : easymaths.free)
... Présentation des critères jurisprudentiels : ils sont au nombre de trois :..... Par la suite, cette partie est divisible ; c'est la première fois que le critère de divisibilité est explicitement utilisé.... (source : fr.wikibooks)

En mathématiques et plus exactement en arithmétique modulaire, un critère de divisibilité est une particularité d'un entier servant à 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 envisageable 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 7485 et la divisibilité par 7, on retranche 2 × 5 à 748 et on redébute avec le résultat ainsi constitué. Le nombre d'origine sera un multiple de p si et uniquement si le nombre final est un multiple de p (voir démonstration plus bas)

Exemples :

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

Exemple et démonstration de critères de divisibilité

Avant en premier lieuer la méthode générale, sont présentées ici quelques critères de divisibilité qui illustrent les techniques utilisées. Une liste particulièrement 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}. _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 s'appelle sigma.

par 2

Énoncé

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

Démonstration

$A = 10B + a_0\,$

10B est toujours multiple de 2 par conséquent A est multiple de 2 si et uniquement si $a 0$ est multiple de 2.

par 3

Énoncé

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

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 : Quand 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}$ )

par 7

Énoncé

Un nombre est divisible par 7 si et uniquement 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.

Exemple : 252

nombre des dizaines : 25; chiffre des unité : 2

On a, 2x2=4 Par conséquent 25-4=21

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$

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

Or, 7 et 10 sont premiers entre eux, par conséquent selon 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$ par conséquent $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}. _1} - 2a_0)$

Démonstration pour un nombre quelconque

Généralement, 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 uniquement si d', $2 q$ et $5 p$ divisent A.

Divisibilité par $2 q$

A est divisible par $2 q$ si et uniquement si le nombre constitué 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

, par conséquent 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 uniquement si le nombre constitué 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

, par conséquent on peut se débarrasser de toute la partie du nombre multiple de

10 p

Divisibilité par de 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 du théorème de Bachet-Bézout. Alors le nombre A sera divisible par de si et uniquement si le nombre $B=\overline{a_n a_{n-1}. _1 }+ ka_0$ est multiple de d'

Démonstration

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

$A \equiv 0 \pmod {d'} \Leftrightarrow 10\times \overline{a_n a_{n-1}. _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}. _1 }+ k 0 \equiv 0 \pmod{d'}$

Exemple

La première difficulté est de trouver cet entier k (le plus proche de 0 envisageable). A titre d'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}$

Par la suite, il suffit de réitérer tout autant que fois que indispensable le principe précédent : pour vérifier, par exemple, que 111258 est divisible par 7

111258 est divisible par 7 si et uniquement si 11125 - 2 × 8, c'est-à-dire 11109, est divisible par 7

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

1092 est divisible par 7 si et uniquement 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 particulièrement 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 de si et uniquement si B l'est .

Exemple : $10ˆ6 \equiv 1 \pmod 7$ par conséquent pour la divibilité par 7, on découpera en tranches de 6.

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

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 en premier lieu 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 exactement 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 toujours de l'ordre du nombre de chiffre du nombre A d'origine. Pour un calcul à la main en base 10, du moins pour les petites diviseurs d, ces méthodes ont un avantage, comparé à la méthode générale par division euclidienne : on évite les calculs intermédiaires de division.

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

Bibliographie

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

Voir aussi

Liste de critères de divisibilité
Ruban de Pascal

Recherche sur Amazon (livres) :

Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Crit%C3%A8re_de_divisibilit%C3%A9.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.

Critère de divisibilité

En mathématiques et plus exactement en arithmétique modulaire, un critère de divisibilité est une particularité d'un entier servant à déterminer si ce nombre est divisible par un autre.

Catégories :

Page(s) en rapport avec ce sujet :

Recherche d'un critère de divisibilité

Exemple et démonstration de critères de divisibilité

par 2

Énoncé

Démonstration

par 3

Énoncé

Démonstration

par 7

Énoncé

Démonstration

Démonstration pour un nombre quelconque

Divisibilité par 2q

Divisibilité par 5p

Divisibilité par de premier avec 10

Remarque sur la complexité algorithmique

Bibliographie

Voir aussi

Recherche sur Amazon (livres) :

Divisibilité par $2 q$

Divisibilité par $5 p$