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 :

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 a0 est le chiffre des unités, a1 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 a0 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

Divisibilité par 2q

A est divisible par 2q si et uniquement si le nombre constitué par les q premiers chiffres (en partant de l'unité) est divisible par 2q

Exemple :

79 532 512 est divisible par 16 (= 24) car 2512 est divisible par 16

Démonstration

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

Divisibilité par 5p

A est divisible par 5p si et uniquement si le nombre constitué par les p premiers chiffres (en partant de l'unité) est divisible par 5p

Exemple :

9864375 est divisible par 125 (= 53) car 375 est divisible par 125

Démonstration

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

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 10n. 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 10m. 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

Voir aussi

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.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu