Ou comment tirer des merveilles de l'algorithme d'Euclide, connu depuis des siècles et ancêtre de toutes les procédures informatiques actuelles.
Énoncé
Ou comment tirer des merveilles de l’algorithme d’Euclide, connu depuis des siècles et ancêtre de toutes les procédures informatiques actuelles.
Dans une note de la seconde édition des Problèmes plaisants et délectables qui se font par les nombres, Claude-Gaspard Bachet de Méziriac, dont le deuxième prénom est parfois orthographié Claude-Gaspar, expose une méthode de résolution d’une équation indéterminée du premier degré à deux inconnues.
Cet exposé montre clairement que Bachet connaissait le théorème dit de Bezout. Voici sa méthode appliquée à un exemple : trouver le premier multiple de 211 qui surpasse de 10 un multiple de 1 007.
En termes modernes, il s’agit de trouver la plus petite solution en nombres entiers de l’équation indéterminée 211 x = 1 007 y + 10, où x désigne le multiplicateur de 211 et y celui de 1 007.
Bachet emploie l’algorithme d’Euclide, qu’il arrête dès que le nombre cherché est obtenu. Il procède par divisions successives.
Il divise 1 007 par 211 : le quotient est 4 et le reste 163. Il divise ensuite 211 par 163 : le quotient est 1 et le reste 48. Puis il divise 163 par 48 : le quotient est 3 et le reste 19. Enfin, il divise 48 par 19 : le quotient est 2 et le reste 10, nombre que l’on voulait atteindre.
Bachet recopie ensuite les quotients dans l’ordre sur une ligne, en rouge.
Sur une deuxième ligne, à droite du dernier quotient, égal à 2, on écrit le nombre 1, puis 0 à droite du 1. On calcule alors de droite à gauche : 1 × 2 + 0 = 2, que l’on écrit à gauche du 1 ; 2 × 3 + 1 = 7, que l’on écrit à gauche du 2 ; 7 × 1 + 2 = 9, que l’on écrit à gauche du 7 ; enfin, 9 × 4 + 7 = 43, que l’on écrit à gauche du 9.
La solution du problème est 43 × 211 = 9 × 1 007 + 10.
Pour trouver d’autres solutions de l’équation 211 x = 1 007 y + 10, on considère les couples ( x , y ) = (43 + 1 007 k , 9 + 211 k ), où k désigne un nombre entier relatif quelconque. On obtient ainsi une infinité de solutions.
Appliquez maintenant la méthode de Bachet aux équations suivantes.
Q1Question 1 sur 4À faire
a) Appliquez la méthode de Bachet à l’équation 14 x = 9 y + 1.
Q2Question 2 sur 4À faire
b) Appliquez la méthode de Bachet à l’équation 18 x = 93 y + 1.
Q3Question 3 sur 4À faire
Pourquoi, dans le cas de l’équation 18 x = 93 y + 1, la méthode de Bachet n’aboutit-elle pas ?
Q4Question 4 sur 4À faire
c) Appliquez la méthode de Bachet à l’équation 18 x = 93 y + 15.
La méthode de Bachet ne permettra pas d’aboutir à 15, mais elle permet d’obtenir un diviseur d de 15, où d désigne ce diviseur. On obtient ainsi un couple solution de l’équation 18 x = 93 y + d. Il suffira ensuite de multiplier les valeurs obtenues par 15 / d pour obtenir le couple solution cherché.