Critere de divisibilite

Critere de divisibilite

Critère de divisibilité

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

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.

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 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 se nomme 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 donc A est multiple de 2 si et seulement 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 : 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})

par 7

Énoncé

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

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)

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' , 2q et 5p divisent A.

Divisibilité par 2q

A est divisible par 2q si et seulement si le nombre formé 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 , donc on peut se débarrasser de toute la partie du nombre multiple de 10q

Divisibilité par 5p

A est divisible par 5p si et seulement si le nombre formé 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 , donc on peut se débarrasser de toute la partie du nombre multiple de 10p

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 du théorème de Bachet-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
111258 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 10n. 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 10m. 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.

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.

Bibliographie

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

Voir aussi

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Crit%C3%A8re de divisibilit%C3%A9 ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Critere de divisibilite de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Critère De Divisibilité — 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… …   Wikipédia en Français

  • Critère de divisibilité — 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… …   Wikipédia en Français

  • Critère — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Un critère (du grec kriterion, de krinein, juger) est un principe auquel on se réfère, ou un moyen qu on utilise, pour établir un jugement. Cette notion… …   Wikipédia en Français

  • DIVISIBILITÉ — L’étude élémentaire de la divisibilité dans l’anneau Z des entiers relatifs résulte de l’existence de la division euclidienne qui entraîne que cet anneau est principal. Les propriétés générales des anneaux principaux sont exposées dans l’article… …   Encyclopédie Universelle

  • Critères de divisibilité — Critère de divisibilité 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… …   Wikipédia en Français

  • Liste De Critères De Divisibilité — Ceci est une liste de critères de divisibilité des nombres écrits en base décimale, exposés sans démonstration. Pour les démonstrations ou les méthodes ayant permis d établir ces critères, voir l article critère de divisibilité. Dans tout cet… …   Wikipédia en Français

  • Liste de criteres de divisibilite — Liste de critères de divisibilité Ceci est une liste de critères de divisibilité des nombres écrits en base décimale, exposés sans démonstration. Pour les démonstrations ou les méthodes ayant permis d établir ces critères, voir l article critère… …   Wikipédia en Français

  • Liste de critères de divisibilité — Ceci est une liste de critères de divisibilité des nombres écrits en base décimale, exposés sans démonstration. Pour les démonstrations ou les méthodes ayant permis d établir ces critères, voir l article Critère de divisibilité. Dans tout cet… …   Wikipédia en Français

  • Ruban de Pascal — Le terme ruban de Pascal renvoie à une technique servant à déterminer si un nombre entier N est divisible par un autre entier D en utilisant les chiffres de l écriture de N dans une base B. Les fondements théoriques de cette méthode relèvent de… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”