Home

MPSI/PCSI

Maths

Algèbre

PGCD et 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.

Salut, bienvenue dans cet exercice dans lequel on va étudier les deux nombres A et B. Alors, le A, il y a 10, 1, donc c'est 1, 1, 1, 1, 1, 10 fois. Et B, c'est 1, 2, 3, 4, 5, 6, 7, 8, 9, tout simplement. Ensuite, première question, on nous dit, calculez le quotient et le reste de la division euclidienne de A par B. En gros, on écrit la division euclidienne de A par B. Donc, ça, on le fait généralement à la calculatrice, parce que là, deux têtes, ce serait assez compliqué. Et on trouve, du coup, que 1, 1, 1, 1, 1, c'est égal à 9 fois 1, 2, 3, 4, 5, 6, 7, 8, 9, plus 10. En gros, que A est égal à 9, ça c'est B, plus 10. Donc voilà, on a bien la division euclidienne de A par B avec le quotient et le reste. Ensuite, calculez le PGCD de A et B. Là, ce qu'il faut faire, c'est faire l'algorithme d'Euclide. On a un petit peu commencé en faisant la division euclidienne de A par B. Maintenant, il faut continuer. Donc, on fait l'algorithme d'Euclide. Donc là, on avait A, B ici. Maintenant, ce qu'il faut faire, c'est diviser celui-là par le reste, donc par 10. Donc celui-ci, c'est 10 fois, on s'arrête ici, donc c'est 10 fois 1, 2, 3, 4, 5, 6, 7, 8, plus 9. Et ensuite, on fait la division euclidienne de 10 par 9. Donc ça fait 10, c'est 9 fois 1, plus 1. On a notre reste, notre dernier reste non nul, parce que dès qu'on arrive à 1, c'est bon, c'est terminé. Donc on reconnaît le PGCD de A et B, du coup, qui vaut 1. Et dernière question, déterminer deux antirelatifs UV, tels que AU plus BV est égal à P. Donc en haut, étant donné qu'ils sont premiers entre eux, on veut que AU plus BV soit égal à 1. On va remonter l'algorithme d'Euclide pour faire ça, pour trouver ce qu'on appelle les coefficients de Bézout. Donc on va remonter cet algorithme ici, pour trouver les coefficients de Bézout. Donc la méthode, c'est remonter l'algorithme. 1, c'est 10 fois 9, on passe le 9 ici. 9, c'est 1, 2, 3, 4, 5, 6, 7, 8, 9, moins 10 fois 1, 2, 3, 4, 5, 6, 7, 8. Donc ça nous fait, comme je disais, on développe, et on se retrouve avec 10 fois 1, 2, 3, 4, 5, 6, 7, 9, moins B, B qui est ici. Et ensuite, 10, on l'écrit comme A moins 9B. Donc on a A moins 9B fois 1, 2, 3, 4, 5, 6, 7, 9, moins B. On développe ça, et on se retrouve avec 1 est égal à 1, 2, 3, 4, 5, 6, 7, 9, moins 1, 1, 1, 1, 1, 1, 1, 1, 2, B. D'accord ? Donc ça fait 111 111 112 B. Donc on a bien nos coefficients U et V qui vérifient que 1, qui est le PGCD de RB, est égal à UA plus BV. Et donc voilà pour cet exercice.

algorithme d’Euclide

RELATED

Recommended videos

PGCD Fibonacci

algorithme d’Euclide

Equations de Bezou

Nos années

Nos principales matières