La clé de la divisibilité

Drapeau jaune : Cet article demande quelques connaissances mathématiques et un peu d’abstraction pour être entièrement compris

---

Est-ce que le nombre 784152 est divisible par 347 ? Cette question, vous vous l’êtes forcément posée à un moment ou un autre de votre vie… Non ? Vraiment ? C’est dommage, je comptais en parler dans cet article. Alors tant pis, j’en traiterai quand même !

Divisibilité

Si nous prenons deux nombres entiers et que nous les multiplions entre eux, cela donne un nouveau nombre entier. Jusque là, rien de nouveau sous le Soleil.

En revanche, lorsque nous faisons une division, tout ne se passe pas aussi bien. Quel est le résultat de la division de 5 par 2, soit le nombre qui, multiplié par 2, vaut 5 ? C’est 2.5, un nombre décimal.

Rassurons-nous tout de même, il arrive que les événements se déroulent de manière plus sympathique : ainsi, 10 divisé par 2 donne 5. On dit alors que 10 est un multiple de 2 et de 5, qu’il est divisible par 2 et 5, ou, inversement, que 5 et 2 sont des diviseurs de 10.

Tout bon matheux pourrait alors se demander s’il est possible, d’un coup d’oeil (ou de deux, trois, mais pas plus), de déterminer si un nombre donné est un multiple d’un autre nombre.

Et non, la calculatrice n’est pas autorisée, non mais !

On cherche alors ce que l’on appelle des critères de divisibilité, des propriétés que doit posséder le premier nombre pour être un multiple du second.

Ces clés, vous en connaissez certaines assez simples :

• si le nombre se termine par 2, 4, 6, 8 ou 0, alors c’est un multiple de 2. C’est ce que l’on appelle plus communément un nombre pair. Ainsi, 1468 (= 734 x 2) est un multiple de 2, car son dernier chiffre est un 8.
• si le nombre se termine par 5 ou 0, alors c’est un multiple de 5 ;
• si le nombre se termine par 0, alors c’est un multiple de 10 ;
• si le nombre se termine par 00, alors c’est un multiple de 100 ;

Et ainsi de suite. Notez d’ailleurs que ces conditions marchent dans les deux sens : si un nombre remplit une condition, il est multiple, et s’il ne la remplit pas, il ne l’est pas. On parle d’équivalence, de conditions nécessaires et suffisantes de divisibilité. Mais tout ça, ce ne sont que des palabres.

A côté, nous avons certains critères de divisibilité un peu plus sophistiqués :

• si la somme des chiffres d’un nombre est un multiple de 9, alors ce nombre est lui-même un multiple de 9.

Prenons un exemple : 4752. Nous avons 4 + 7 + 5 + 2 = 18, qui est un multiple de 9. Ainsi, 4752 est aussi un multiple de 9 ; il vaut par ailleurs 528 x 9. Alors, tout ça, c’est bien beau, mais on est en droit de se demander d’où ça sort.

Décomposition et congruence

Le principe est assez simple : on va, plutôt que de considérer le nombre tout entier, le découper en petits fragments : unités, dizaines, centaines… Reprenons le nombre 4752 de tout à l’heure :

4752 = 4 x 1000 + 7 x 100 + 5 x 10 + 2

On peut encore faire un peu mieux, en décomposant 10, 100, et 1000 comme suit :

4752 = 4 x (999 + 1) + 7 x (99 + 1) + 5 x (9 + 1) + 2

Pourquoi s’embêter ainsi ? Poursuivons les calculs, en développant et en réordonnant :

4752 = (4 x 999 + 7 x 99 + 5 x 9) + (4 + 7 + 5 + 2)

Avec cette égalité, on se rend compte que si 4752 est un multiple de 9, alors le membre de droite l’est aussi. Nous avons deux parties, symbolisées par les parenthèses dans l’expression.

• D’abord, il y a 4 x 999 + 7 x 99 + 5 x 9… qui est un multiple de 9 ! Nous n’avons donc pas besoin de nous en occuper.
• Puis il y a 4 + 7 + 5 + 2… Tiens, revoilà la somme des chiffres.

Ainsi, on retrouve notre résultat : 4752 est un multiple de 9 si est seulement si 4 + 7 + 5 + 2 l’est aussi.

Ce que nous avons fait, c’est retirer le plus gros multiple de 9 possible à 10, à 100, à 1000, et si le nombre était plus grand, nous aurions pu procéder de la même manière avec 10000, 100000… A chaque fois, il nous restait 1. On dit que 10, 100, 1000 sont congrus (ou égaux) à 1 modulo 9

Essayons maintenant avec 7. 4752 est-il un multiple de 7 ? Reprenons notre décomposition.

4752 = 4 x 1000 + 7 x 100 + 5 x 10 + 2
4752 = 4 x (7 x 142 + 6) + 7 x (14 x 7 + 2) + 5 x (7 x 1 + 3) + 2
4752 = (4 x 7 x 142 + 7 x 14 x 7 + 5 x 7) + (4 x 6 + 7 x 2 + 5 x 3 + 2 x 1)

Là encore, nous avons un multiple de 7 entre les premières parenthèses. On conclut rapidement que 4752 est un multiple de 7 si et seulement si 4 x 6 + 7 x 2 + 5 x 3 + 2 x 1 = 55 est un multiple de 7 également, ce qui en l’occurrence, n’est pas le cas.

Ici, on ne se contente pas d’additionner les nombres, il faut les multiplier par une certaine quantité qu’on appelle la clé de divisibilité.

La clé de divisibilité par un nombre est en fait une suite périodique, qui se répète à l’infini. Pour 9, il s’agit de la suite (1, 1, 1, 1, …). Pour 7, c’est un peu plus compliqué, puisque l’on doit appliquer la clé (1, 3, 2, 6, 4, 5, 1, 3, 2…). Il faut multiplier le chiffre des unités par le premier nombre de la clé, le chiffre des dizaines par le deuxième, celui des centaines par le troisième, et ainsi de suite, puis additionner le tout.

Alors, c’est bien joli, mais on aimerait tout de même quelque chose d’un poil plus simple qu’une série de 6 nombres qui se répètent.

Clé à l’unité

Nous allons procéder à un nouveau découpage de notre nombre, plus simple, en séparant simplement les unités du restes du nombre :

4752 = 475 x 10 + 2

Nous allons désormais multiplier à droite et à gauche par un certain nombre, c

4752 c = 475 x 10 c + 2 c

L’astuce consiste à trouver un c tel que notre facteur 10c soit congrus à 1 modulo 7 – si on lui retire le plus grand multiple de 7 possible, on obtient 1. C’est le cas pour c = 5, puisque 10c = 50 = 49 + 1. Alors,

4752 x 5 = (475 x 49) + (475 + 2 x 5)

Ainsi, si 7 divise le membre de gauche, il divise aussi le membre de droite, et donc divise 475 + 2 x 5.

Mais attention ! A gauche, nous n’avons pas 4752 mais 4752 x 5, ce qui n’est pas vraiment le résultat escompté. Passons ce détail pour le moment, les plus curieux et les moins allergiques à l’arithmétique trouveront la solution à ce problème un peu plus bas.

Ainsi, 4752 est divisible par 7 si et seulement si 475 + 2 x 5 l’est aussi. Est-ce que c’est le cas ? Eh bien, appliquons de nouveau notre procédé !

475 + 2 x 5 = 485 ; 48 + 5 x 5 = 73 qui n’est pas un multiple de 7

Et ainsi, voici notre réponse. Résumons donc notre procédé.

• On multiplie le chiffre des unités par notre clé unité c (5 dans notre cas)
• On ajoute le résultat obtenu au nombre des dizaines – pas seulement le chiffre des dizaines ! On prend tout le reste
• On recommence ainsi si besoin

Et cela peut fonctionner avec beaucoup de nombres. Pour un diviseur d, il suffit de trouver un nombre c tel que 10c – 1 soit un multiple de d. Par exemple, pour savoir si un nombre est divisible par 19, il suffit de prendre la clé c = 2, puisque 10 x 2 – 1 = 19. Pour 11, on peut prendre c = 10 (10 x 10 – 1 = 99, multiple de 11).

475 + 10 x 2 = 495 ; 49 + 5 x 10 = 99 ; 99 est un multiple de 11, donc 4752 aussi.

Une question peut alors nous traverser l’esprit : un tel procédé marche-t-il pour n’importe quel diviseur ?

Ca commence par un Bézout, ça finit par un Gauss

Ah, je suis content, j’ai pu la caser celle-là…

Nous allons devoir nous en remettre à deux théorèmes de l’arithmétique pour vérifier que tout fonctionne bien ! Il va vous falloir quelques petites notions dans le domaine pour saisir les prochaines lignes (enfin, savoir ce que sont des nombres premiers entre eux, et ne pas être dégoûté par le calcul littéral).

Théorème de Bezout : Soient a et b deux entiers. Il existe c et d deux entiers relatifs tels que ac + bd = 1 si et seulement si a et b sont premiers entre eux.

Dans notre cas, on étant donné le diviseur d, on cherchait une clé c telle que 10c – 1 soit un multiple de d, autrement dit, 10c – 1 = kd pour un certain k, ou encore

10c – kd = 1

Nous voyons déjà un premier souci : si d et 10 ne sont pas premiers entre eux, ce théorème nous assure que c’est peine perdu, on ne trouvera jamais de tels nombres c et k. Exit donc les multiples de 2 et de 5, pas de clé unité pour ceux-là.

En revanche, si d et 10 sont premiers entre eux, alors l’existence de tels entiers est assurée ! Par ailleurs, on peut également noter que c et d sont alors premiers entre eux… Ce qui nous amène au second théorème !

Théorème de Gauss : Soient a, b et c trois entiers, si a divise bc et a est premier avec b, alors a divise c.

Un peu plus haut, nous nous retrouvions à nous demander si « 7 divise 4752 » et « 7 divise 4752 x 5 » revenaient ou non à la même chose. Eh bien, puisque 7 et 5 sont premiers entre eux, le second implique le premier.

Et ce qui est bien, c’est que nous avons montré que notre clé et notre diviseur sont toujours premiers entre eux. Formidable, la boucle est bouclée. Vous voilà d’attaque pour la divisibilité !

Pour compléter

• Des clés de divisibilité sur Nombres : Curiosité, théories et usages
• Et une autre sur Wikipedia

 

Publicité