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 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 , c'est-à-dire que a0 est le chiffre des unités, a1 est le chiffre des dizaines, etc.
d'où
Le symbole 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
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.
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 )
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,
On a :
- Or, 7 et 10 sont premiers entre eux, par conséquent selon le théorème de Gauss :
Réciproquement, si
- alors
- Or,
par conséquent
- On obtient :
Conclusion :
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
où d'est premier avec 10
- d divise A si et uniquement si d', 2q et 5p divisent A.
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 . 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
est multiple de d'
Démonstration
- Comme k est premier avec d', on peut multiplier la congruence par k en conservant l'équivalence, et comme
, on a
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
, et pour d'= 93, cet entier est 28 car
- 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 . 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 : 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) : |
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.