Nous allons maintenant pouvoir résoudre toutes les équations diophantiennes du type AX plus BY égale à C. Les nombres A, B, C sont donnés, ce sont trois entiers. Les inconnus sont X et Y et elles aussi sont des entiers. Tout d'abord, le premier point nous fournit un critère simple pour savoir s'il y a des solutions ou s'il n'y en a pas.
Cette équation possède des solutions, x et y entières, si et seulement si le PGCD de a et de b divise c. Deuxième point, si le PGCD de a à b divise c, alors il y a des solutions, et il y en a même une infinité, que l'on sait calculer. Les x sont de la forme x0 plus αk, et les y de la forme y0 plus βk. avec k parcourant l'ensemble des entiers et x0, y0, α, β sont des entiers que l'on va calculer en fonction de a, b et c.
Nous n'allons pas démontrer cette proposition ici mais plutôt détailler comment résoudre complètement chaque équation particulière. Voyons sur un exemple comment résoudre les équations du type AX plus BY égale C. Nous cherchons tous les couples XY, solution de l'équation 161X plus 368Y égale 115. Bien sûr, nous cherchons X et Y entiers.
Nous allons résoudre ce problème en trois étapes. 1. Y a-t-il des solutions ? 2. Si oui, alors on trouve une solution particulière. Et 3. On en déduit toutes les solutions.
Commençons par déterminer s'il existe des solutions. C'est le théorème de Bezou qui apporte la réponse. Si le PGCD de A et B divise C, alors il existe des solutions. Nous allons donc calculer le PGCD de 161 et 368 avec l'algorithme d'Euclide. On écrit la division euclidienne 368 est égale à 161 fois 2 plus 46, 161 est égale à 46 fois 3 plus 23, et 46 est égale à 23 fois 2. Le PGCD de 161 et 368 est donc 23. Est-ce que le PGCD divise C ?
Oui. car 115 est égal à 5 fois 23. Donc par le théorème de Bezou, il existe des solutions entières à l'équation 161x plus 368y égale 115. Jusqu'ici, nous savons qu'il existe des solutions de notre équation. Nous allons en expliciter une.
Cette solution particulière correspond aux coefficients de Bezou que l'on obtient en remontant l'algorithme de Clid. Reprenons les calculs qui ont conduit au PGCD. L'égalité 161 est égale à 46 fois 3 plus 23 permet d'écrire le PGCD 23 sous la forme 23 est égale à 161 plus 46 fois moins 3. Ensuite, on remplace 46 par 368 moins 2 fois 161 et on simplifie.
Et nous obtenons 161 fois 7 plus 368 fois moins 3 est égal à 23. Mais ceci n'est pas tout à fait une solution de notre équation, car nous voulons trouver x et y tels que 161x plus 368y égale 115 et pas 23. Mais 115 est égal à 5 fois 23. Donc en multipliant par 5, nous obtenons 161 fois 35 plus 368 fois moins 15 est égal à 115. Voilà une solution particulière de notre équation, le couple x0, y0 égale à 35 moins 15. Nous savons qu'il existe des solutions. Nous avons même trouvé une solution particulière x0, y0 et nous allons pouvoir en déduire toutes les solutions. Supposons que le couple x, y soit une solution de notre équation. Nous avons donc l'égalité 161x plus 368y est égale à 115. Nous allons déterminer la forme de x et y. Nous avons aussi déterminé une solution particulière x0, y0.
Donc nous avons l'égalité 161x0 plus 368y0 égale 115. Même si nous savons que x0 égale 35 et y0 égale moins 15, nous n'avons aucun intérêt à substituer ces valeurs dès maintenant. Soustrayons ces deux égalités. Cela nous conduit à 161 fois x moins x0 plus 368 fois y moins y0 égale 0. La constante 115 a disparu.
Rappelons-nous que 161 et 368 sont des multiples de 23, qui est leur PGCD, et donc en divisant par 23, on obtient une égalité plus simple, 7 facteur de x moins x0 est égal à moins 16 facteur de y moins y0. Cette équation implique premièrement que 7 divise 16 fois y moins y0. Mais 7 et 16 sont premiers entre eux, donc par le lème de Gauss, 7 divise y moins y0. En d'autres termes, il existe un entier k tel que y moins y0 est égal à 7 fois k.
Voilà pour y. Cherchons la forme de x. Nous repartons de l'égalité 7 facteur de x moins x0 est égal à moins 16 facteur de y moins y0. Et l'on remplace y moins y0 par 7 fois k.
Et ainsi, on trouve x moins x0 est égal à moins 16 fois k. C'est bien le même entier k pour x et pour y. Donc notre couple de solutions est de la forme x est égal à x0 moins 16 fois k et y est égal à y0 plus 7 fois k.
Il n'est pas dur de voir que tout couple de cette forme est solution de notre équation. On se rappelle maintenant des valeurs de x0 et y0. Et nous obtenons toutes les solutions de l'équation 161x plus 368y égale 115. Ce sont les couples d'entiers x et y, tels que x est égal à 35 moins 16 fois k, et y est égal à moins 15 plus 7 fois k, avec k parcourant l'ensemble des entiers z. Attention, c'est bien le même k pour x et y.