Home

MPSI/PCSI

Maths

Algèbre

PGCD et algorithme d’Euclide

Dans cet exercice, nous avons résolu quatre équations diophantiennes. Pour résoudre une équation diophantienne, nous commençons par trouver une solution particulière. Si cela n'est pas évident, nous utilisons une méthode spécifique pour garantir une solution. La solution générale se calcule en ajoutant ou soustrayant un coefficient devant l'autre inconnu. 
Dans la première équation, le PGCD de 2 et 5 est 1. Nous trouvons facilement une solution particulière en prenant x = -1 et y = 1. La solution générale est alors écrite comme x = -1 - 5k et y = 1 + k. 
Dans la deuxième équation, le PGCD est 17. Après simplification, nous obtenons 19x - 23y = 6. En appliquant l'algorithme de Clide, nous trouvons une solution particulière qui est x = -216 et y = -180. La solution générale est alors x = -216 + 23k et y = -180 + 19k. 
Dans la troisième équation, le PGCD est 9. Après simplification, nous obtenons 18x + 23y = 3. En appliquant à nouveau l'algorithme de Clide, nous trouvons une solution particulière qui est x = 27 et y = -21. La solution générale est alors x = 27 + 23k et y = -21 + 18k. 
Enfin, dans la dernière équation, le PGCD est 13 mais il ne divise pas 15, ce qui signifie qu'il n'y a pas de solution.

Salut, bienvenue dans cet exercice où on va résoudre quatre équations diophantiennes. Il y en a qui vont être plus ou moins faciles que d'autres. Pour rappel, la méthode pour résoudre une équation diophantienne, c'est qu'on commence par trouver une solution particulière, si elle saute aux yeux, sinon on verra la méthode pour en trouver une à coup sûr, qui généralement n'est pas forcément évidente. Donc on trouve une solution particulière, et ensuite, la solution générale, c'est la solution particulière plus ou moins le coefficient qui est devant l'autre inconnu. On va voir ça en place et vous allez voir que ça va se décanter. C'est parti pour la première. Le PGCD de 2 et de 5, c'est 1. 1 divise 3, il n'y a pas de souci, ça admet une solution. Ici, on peut voir qu'on veut que ce soit égal à 3. Une solution particulière, là, elle saute aux yeux. 5 moins 2, ça fait 3. Donc on prend x égale moins 1, y égale 1, ça nous fait 3. Donc on a notre solution particulière. Moins 1, 1, on les écrit là pour la solution générale. Et donc, comme je disais, la méthode à faire, c'est qu'on prend la solution particulière. Il y en a un des deux, soit x, soit y, on va mettre un moins devant le coefficient de l'autre. Moi, j'ai choisi de le faire avec x. Donc je dis x, c'est moins 1, moins 5k, d'accord ? Parce qu'ici, on a plus 5y, donc je dis moins 5k. Et du coup, vu que j'ai mis le moins au niveau du x, le y, il n'y aura pas de moins, donc ça veut dire que ce sera 1, la solution particulière, plus le coefficient de x sans le moins, parce qu'on l'a déjà mis à l'autre, fois k. Et voilà l'ensemble des solutions. Aussi simple que ça. Une fois qu'on a trouvé une solution particulière, l'ensemble des solutions s'écrit en deux lignes, tout simplement. Pour la deuxième, la solution particulière va beaucoup moins sauter aux yeux. Déjà, on va vérifier s'il existe une solution. Là, l'algorithme de Clide nous donne que le PGCD de ces deux nombres, c'est 17, d'accord ? Je ne l'ai pas fait parce qu'on l'a déjà vu dans d'autres exercices, et en plus, on le voit en terminale, entre deux nombres pour trouver le PGCD. Donc, on trouve que c'est 17. 17 divise 612, c'est 17 fois 36. Du coup, il y a bien une solution. Et on va même simplifier, parce qu'en fait, ce qu'on veut, c'est les solutions de cette équation. On a le droit, c'est une équation, on a le droit de diviser à gauche, à droite, ou de multiplier par un nombre, si ça nous arrange. Là, on sait que tous les coefficients, aussi bien 323, 391 et 612, on sait qu'ils sont douze divisibles par 17. Donc, en fait, on va se simplifier les calculs en divisant par 17 tous les membres de cette égalité. Donc, cette équation, elle est équivalente à 19X moins 23Y est égale à 6. On sait que 19 et 23 sont premiers entre eux, parce qu'on a divisé par le PGCD de 323 à 391. Donc, on sait qu'ils sont premiers entre eux. Donc, on sait qu'il y a une solution à cette équation. Maintenant, encore une fois, la solution particulière, elle ne saute pas forcément aux yeux. 19, 23 et 36, comment on fait pour combiner tout ça ? Ça ne saute pas aux yeux. Si pour vous, ça saute aux yeux, très bien. Vous avez votre solution particulière, et on fait le même travail ici. Personnellement, moi, ça ne me sautait pas aux yeux. Donc, voilà. La méthode, quand on n'a pas une solution particulière qu'on voit immédiatement, c'est de faire l'algorithme de Clyde avec les coefficients qui sont là, pour ensuite le remonter, pour trouver les coefficients de Bézout, parce qu'on sait qu'ils sont premiers entre eux. Donc, ce qu'on a, c'est que 23, c'est 19 plus 4, 19, c'est 4 fois 4 plus 3, et 4, c'est 3 fois 1 plus 1. On arrive à 1, c'est bon, c'est terminé. On va remonter ça. 1, c'est 4 moins 3. 3, c'est 19 moins 4 fois 4. On écrit ça, on développe. On a 5 fois 4 moins 19. Et 4, c'est 23 moins 19. On distribue, sans faire les calculs. On n'a que 1, c'est 5 fois 23 moins 6 fois 19. Mais, nous, ce qu'on voulait, c'est égal à 36, pas égal à 1. Donc là, on a bien des coefficients. Ici, on a bien 19 fois quelque chose, moins 23 fois quelque chose. Bon, il faut adapter avec les signes, tout ça. Mais, nous, on veut 36. Donc, on multiplie par 36, tout simplement. Et on se retrouve avec 36 est égal à 180 fois 23, moins 219 fois 19. Donc là, on a nos coefficients, qui sont un peu grands, pas forcément exploitables. Ce n'est pas grave, on ne nous demande pas une solution exploitable facilement. On demande juste une solution, toutes les solutions après. Sauf que là, il faut bien faire attention à ne pas mélanger, parce que moi, 180 fois 23 est moins 219 fois 19. Pardon, moins 216 fois 19. Mais là, on veut une solution pour X. Donc, pour X, je prends moins 216. Et là, on a moins 23Y. Et moi, j'ai du positif ici, donc j'ai moins 180. Donc, une solution particulière, c'est moins 216, moins 180. Et du coup, l'ensemble des solutions, c'est pareil. Donc là, on réécrit notre solution particulière. Devant le X, on prend moins le coefficient de Y, donc moins moins 23, donc ça fait plus 23, on multiplie par K. Et devant le Y, on prend le coefficient devant le X, et on multiplie par K, donc ça fait plus 19K. Donc voilà, l'ensemble des solutions pour la deuxième équation. Et la troisième équation, maintenant, c'est 162X plus 207Y, qui est égale à 27. Pareil, on va faire le travail du PGCD. Donc, le PGCD de 169, 207, c'est 9. 9, ça divise 27, il n'y a pas de souci. Et on peut diviser par le PGCD, on se retrouve avec l'équation 18X plus 23Y est égale à 3. Pareil, on va chercher une solution particulière. Là, ça ne saute pas forcément aux yeux. Encore une fois, si pour vous, ça saute aux yeux, une solution particulière, allez-y, ne faites pas tout ce travail, ça ne sert à rien, ça ralentit. Mais si ça ne saute pas aux yeux, il en faut bien une, donc on n'a pas le choix. On fait l'algorithme de Clyde, voilà. On trouve 1, tant mieux, parce qu'étant donné qu'on a divisé par le PGCD, ils sont censés être premiers entre eux, donc si on ne trouve pas 1, c'est qu'il y a un problème. Donc là, on trouve bien 1, ça nous rassure. On fait le même travail que tout à l'heure. 1, c'est 3 moins 2. 2, on écrit comme 5 moins 3, parce qu'on passe ça de l'autre côté. On enchaîne, on enchaîne, maintenant on sait faire. Et on n'a que 1, donc là, on a les coefficients de Bézout. 1, c'est 9 X 18 moins 7 X 23. Donc là, on a... Pardon, on a ici 9, ici moins 7, sauf que ça ne nous fait pas 3. Encore une fois, ça nous fait 1, donc on va juste tout multiplier par 3. Et comme ça, on a 27 X 18 moins 21 X 23 est bien égal à 3. Donc, une solution particulière. Cette fois-ci, contrairement à la question juste avant, cette fois-ci, ils sont bien dans l'ordre. On a bien 18 X quelque chose, du coup 27, et 23 X moins 21. Donc, on a bien X est égal à 27 et Y est égal à moins 21. Donc, pareil, l'ensemble des solutions. Donc, on met 27 moins 21. Devant le X, on met moins le coefficient devant le Y, donc on met moins 23 fois K. Et devant Y, on met le coefficient devant le X, donc 18 fois K. Et donc, voilà pour l'ensemble des solutions de la troisième équation. La dernière maintenant. 221 X plus 247 Y est égal à 15. On fait le PGCD. Le PGCD... Où est-ce que c'est ? Le PGCD de 221 et 247, c'est 13. Eh bien, 13 divise pas 15. Donc là, l'équation n'admet aucune solution. Et voilà ce qui conclut cet exercice.

Equations de Bezou

RELATED

Recommended videos

PGCD Fibonacci

algorithme d’Euclide