algorithme d’Euclide

Dans cet exercice, nous étudions les nombres A et B. A est composé de neuf fois le chiffre 1, et B est simplement la séquence des chiffres de 1 à 9. La première question demande de calculer le quotient et le reste de la division euclidienne de A par B. En effectuant cette division, nous trouvons que A est égal à 9 fois B plus 10, ce qui donne le quotient et le reste de la division. Ensuite, nous devons trouver le PGCD (Plus Grand Commun Diviseur) de A et B. Pour cela, nous utilisons l'algorithme d'Euclide, que nous commençons en effectuant la division euclidienne de A par B. Ensuite, nous continuons l'algorithme en divisant le reste précédent (10) par 9, et ainsi de suite, jusqu'à ce que nous obtenions un reste nul ou égal à 1. Nous reconnaissons alors que le PGCD de A et B est égal à 1. La dernière question consiste à déterminer deux antirelatifs UV tels que AU plus BV soit égal à 1. Pour ce faire, nous remontons l'algorithme d'Euclide en utilisant les résultats précédents. En développant les calculs, nous obtenons que 1 est égal à 111 111 112 fois B. Ainsi, nous trouvons les coefficients U et V qui vérifient la condition demandée. Voilà pour le résumé SEO friendly de cet exercice.