Aller au contenu

La méthode de Bachet

mars 2016
Ajouter aux favorisSignaler une erreur

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.

Indice offert

Commence par écrire la division euclidienne de 14 par 9. Reprends ensuite, à chaque ligne, le diviseur et le reste précédents, jusqu’à faire apparaître le reste recherché 1, puis relève les quotients dans leur ordre.
Q2Question 2 sur 4À faire
b) Appliquez la méthode de Bachet à l’équation 18 x = 93 y + 1.

Indice offert

Effectue la division euclidienne de $93$ par $18$ : cherche le quotient entier et le reste. Utilise ensuite ce reste comme nouveau diviseur.
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 ?

Indice offert

Effectue la division euclidienne de $93$ par $18$ : cherche le quotient entier et le reste, strictement inférieur à $18$. Recommence ensuite en divisant $18$ par le reste obtenu.
Q4Question 4 sur 4À faire
c) Appliquez la méthode de Bachet à l’équation 18 x = 93 y + 15.

Indice offert

Divise $93$ par $18$, puis recommence avec $18$ et le reste obtenu. Repère le dernier reste non nul : note-le $d$, car c’est le plus grand commun diviseur de $18$ et $93$.
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é.

Problème suivant : La méthode des différences finies

Créez votre compte gratuit

Avec un compte, les indices sont gratuits. La vérification de vos réponses et l’aide de Tablo fonctionnent avec des crédits IA, inclus chaque mois dans l’abonnement.