Fabriquez vos propres critères de divisibilité

Tout le monde connaît les critères de divisibilité par 2, par 3, par 4, par 5 ou par 6. Je vous les rappelle : un nombre est divisible par

  • 2 si son dernier chiffre est 0, 2, 4, 6 ou 8
  • 3 si la somme de ses chiffres est elle-même divisible par 3
  • 4 si ses deux derniers chiffres forment un nombre divisible par 4
  • 5 s’il se termine par 0 ou 5
  • 6 s’il est divisible par 2 et par 3

Cependant, si on demande de dire si un nombre est divisible par 7, je ne suis pas sûr que tout le monde sache répondre. En Novembre 2019, un jeune Nigérian vivant au Royaume-Uni du nom de Chika Ofili a reçu un « TruLittleHero Awards » pour avoir découvert un critère de divisibilité par 7.  Voici l’énoncé du test de Chika (comme il l’a nommé) pour lequel il a été récompensé:

Un nombre est divisible par 7 si, et seulement si, la somme de son nombre de dizaines et de 5 fois son nombre des unités est divisible par 7.

Même si ce critère n’était en fait pas du tout nouveau et qu’il était déjà connu depuis longtemps, c’est une belle performance pour un jeune de cet âge de l’avoir trouvé.

Le test de Chika permet en particulier de savoir si les Sept nains sont bien au complet.

Un exemple

Voyons comment utiliser ce critère pour déterminer si 651 est divisible par 7. Le nombre de dizaines est 65 et le nombre des unités est 1. On calcule:

65+ 5 \times 1 = 70

Comme 70 est un multiple de 7, il en va de même pour 651 qui est donc divisible par 7. Bien entendu, on peut répéter cette opération si l’on tombe sur un nombre dont on ne voit pas tout de suite qu’il est divisible par 7. Par exemple, pour savoir si  4826 est divisible par 7, on calcule successivement:

482 + 5 \times 6 = 512

51 + 5 \times 2 = 61

6 + 5 \times 1 = 11

Comme 11 n’est pas divisible par 7,  4826 non plus n’est pas divisible par 7. Facile, non ?

Une démonstration

Ce critère ayant quand même été parachuté brutalement, il serait de bon ton de le démontrer afin de comprendre pourquoi il marche et, pour cela, nous allons utiliser le très élégant langage des congruences inventé par Gauss. On considère un nombre n dont le nombre de dizaines est a et le nombre d’unités est b. Autrement dit, n= 10a +b.

• Si n est divisible par 7, alors n \equiv 0 \mod[7] donc

10a+b \equiv 0 \mod[7]

En multipliant les deux membres par 5, on obtient:

50a + 5b \equiv 0 \mod[7]

Comme 50 \equiv 1 \mod[7] (car 50 = 7 \times 7 + 1) alors

a + 5b \equiv 0 \mod[7]

ce qui montre que la somme du nombre de dizaines et de 5 fois le nombre des unités est divisible par 7.

• Réciproquement, si a + 5b \equiv 0 alors en multipliant par 10 de chaque côté,

10a+50b \equiv 0 \mod[7]

d’où

10a+b \equiv 0 \mod[7]

ce qui veut bien dire que n=10a+b est divisible par 7.

Analyse de la démonstration

Le point clé de cette démonstration est d’avoir multiplié les deux membres par 5 pour le sens direct et par 10 pour la réciproque. Les nombres 5 et 10 ne sont pas là par hasard et un lien les unis modulo 7 : le nombre 5 \times 10 est un multiple de 7 augmenté de 1, c’est-à-dire que 5 \times 10 \equiv 1 \mod[7]. On dit aussi que 5 est inversible modulo 7 et que « son » inverse est 10 (et, inversement si je puis dire, le nombre 10 est inversible modulo 7 et « son » inverse est 5).

Il se trouve qu’il existe d’autres nombres qui sont inversibles modulo 7 (en fait, tous sauf les multiples de 7 mais c’est une autre histoire). Si nous prenons par exemple le nombre 4, dont l’inverse modulo 7 est 2 (car 4 \times 2 \equiv 1 \mod[7]) alors, en reprenant la démonstration précédente, mais en multipliant par 4, on a

10a +b \equiv 0 \mod[7] \Longrightarrow 40a + 4b \equiv 0 \mod[7] \Longrightarrow 5a + 4b \equiv 0 \mod[7]

car 40 \equiv 5 \mod[7]. Réciproquement, en multipliant par 2,

5a+4b \equiv 0 \mod[7] \Longrightarrow 10a + 8b \equiv 0 \mod[7] \Longrightarrow 10a + b \equiv 0 \mod[7]

car 8 \equiv 1 \mod[7]. Nous venons donc fièrement de fabriquer un nouveau critère de divisibilité qui est le suivant:

Un nombre est divisible par 7 si, et seulement si, la somme de 5 fois son nombre de dizaines et de 4 fois son nombre des unités est divisible par 7.

Par exemple, pour voir que 105 est bien divisible par 7, il suffit de voir que 5\times 10 + 4 \times 5 = 70 est lui-même divisible par 7. Nous méritons aussi notre récompense !

Des critères de divisibilité pour d’autres nombres

Les critères de divisibilité par 7, c’est bien (quoique vous n’auriez peut-être pas dit cela avant de lire cet article) mais les triskaïdékaphobes veulent eux savoir si les nombres qu’ils manipulent sont des multiples de 13. Et bien, je leur dis de prendre un nombre inversible modulo 13 et de faire leur propre critère. Par exemple, si on prend le nombre 2 (qui est bien inversible modulo 13 car 2 \times 20 = 3 \times 13 + 1) alors

2 \times (10a + b) = 20a + 2b \equiv 7a + 2b \mod[13]

On en déduit le critère de divisibilité par 13 suivant:

Un nombre est divisible par 13 si, et seulement si, la somme de 7 fois son nombre de dizaines et de 2 fois son nombre des unités est divisible par 13.

Des critères plus simples

Vous avez probablement dû vous insurger en lisant le critère précédent (sinon, vous devriez). Multiplier un nombre de dizaines par 7 n’est clairement pas chose aisée de tête. Tous ces critères que l’on peut créer ne se valent donc pas tous, et ceux pour lesquels on doit multiplier le nombre de dizaines par un nombre supérieur ou égal à 2 sont évidemment moins pratiques. L’idéal est donc d’avoir un critère où il n’y a pas besoin de multiplier le nombre de dizaines, comme dans le critère énoncé par le jeune Chika. Reprenons donc le nombre 13 et trouvons en un critère de divisibilité plus simple.

Si l’on en croit les démonstrations précédentes,  cela revient donc à trouver un nombre k tel que k \times 10 \equiv 1 \mod[13]. Autrement dit, il s’agit de trouver un inverse de 10 modulo 13.

Pour cela, on peut utiliser un algorithme bien connu qu’on nomme l’algorithme d’Euclide étendu (que je ne détaillerai pas ici… mais il existe des calculateurs en ligne). Sachant que 4 est un inverse de 10 modulo 13, en mutlipliant n=10a +b par 4, il vient

10a + b \equiv 0 \mod[13] \Longrightarrow 40a + 4b \equiv 0 \mod[13] \Longrightarrow a + 4b \equiv 0 \mod[13]

La réciproque étant aussi vraie, on en déduit alors le critère de divisibilité par 13 suivant:

Un nombre est divisible par 13 si, et seulement si, la somme de son nombre de dizaines et de 4 fois son nombre des unités est divisible par 13.

Généralisation

Vous l’aurez compris, pour obtenir un critère de divisibilité simple par un nombre m donné, il suffit de trouver un inverse de 10 modulo m. Par exemple, comme un inverse de 10 modulo m=19 est 2, alors un nombre sera divisible par 19 si, et seulement si, la somme de son nombre de dizaines et de 2 fois son nombre des unités est divisible par 19.

Une dernière question se pose alors: que se passe-t-il si 10 ne possède pas d’inverse modulo m ? Par exemple, si m=14 ou m=420, un tel inverse de 10 n’existe pas (on peut en fait montrer qu’un inverse existe si, et seulement si, 10 et m sont premiers entre eux c’est-à-dire si, et seulement si, m n’est divisible ni par 2, ni par 5). Dans ce cas, il faut se ramener à d’autres nombres, un peu comme pour savoir si un nombre est divisible par 6 il faut et il suffit qu’il soit divisible par 2 et 3.

Prenons le cas de m=420: comme les plus grandes puissances de 2 et de 5 divisant 420 sont 2^2 et 5 et que 420 = 2^2 \times 5 \times 21, il suffit alors de connaitre un critère de divisibilité par 4, par 5 et par 21. Vous connaissez déjà des critères de divisibilité par 4 et 5, et vous venez d’apprendre comment créer un critère de divisibilité par 21 donc vous pouvez facilement savoir si un nombre est divisible par 420. Mieux encore: comme 21 = 3 \times 7, il suffit en fait de connaître un critère de divisibilité par 3 et par 7.

Plus généralement, pour obtenir un critère de divisibilité par un nombre quelconque, il suffit de connaître des critères de divisibilité par 2^k et par 5^k mais aussi de fabriquer des critères de divisibilité par p^kp est un nombre premier différent de 2 et de 5. Et ça, vous savez le faire maintenant.

Notes:

Cet article, publié dans Arithmétique, Nombres, est tagué , , , , , , , , . Ajoutez ce permalien à vos favoris.

3 commentaires pour Fabriquez vos propres critères de divisibilité

  1. Christophe dit :

    Merci pour cet article clair et intéressant.
    Une remarque : on atteint rapidement les limites de l’exercice avec des nombres premiers relativement peu élevés. La méthode apparaît peu exploitable pour détecter des multiples de 41 par exemple, dans la mesure où l’inverse de 10 mod(41) est 37.

    J'aime

  2. blogdemaths dit :

    Merci pour vos encouragements !

    Vous avez parfaitement raison pour votre remarque. Cependant, on peut s’en sortir dans le cas de 41: comme 37 \equiv -4 \mod[41], on pourrait donner le critère suivant: un nombre est divisible par 41 si, et seulement si, la différence de son nombre de dizaines et de 4 fois son nombre d’unités est divisible par 41

    J'aime

Votre commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l’aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l’aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.