Équations diophantiennes

$ax + by = c, \textrm {pgcd} (a,b) = d \quad \textrm {avec} \quad d \neq 1.$

Si $d$ ne divise pas le second membre $c,$ l'équation est impossible, n'a pas de solutions. Nous avons donc une condition nécessaire d'existence des solutions : $\textrm {pgcd} (a,b)$ divise $c.$ Nous supposerons dorénavant cette condition satisfaite.

$ax + by = c, \textrm {pgcd} (a,b) = d$ et $d$ divise $c.$

On pose $a = da', b = db', c = dc'$ et l'on sait que $\textrm {pgcd} (a',b') = 1.$

On reporte dans l'équation, $da'x + db'y = dc',$ on simplifie l'équation et on obtient une nouvelle équation, qui a les mêmes solutions que la précédente,

$\begin {array}{cccc}ax + by&=&c&(1)\\a'x+b'y&=&c'&(2)\end {array}$

(on se ramène donc au cas $\textrm {pgcd} (a,b) = 1).$

On détermine une solution $(x_0, y_0)$ de l'équation $a'x + b'y = 1$ en utilisant l'algorithme d'Euclide, comme on a vu précédemment.

On a un couple $x = x_0 c', y = y_0 c',$ solution des équations (1) et (2).

de l'équation de $a'x + b'y = c'.$

$\begin {array}{cccc}&a'x+b'y&=&c'\\&a'x_0 + b'y_0&=&c'\\\textrm {et par soustraction :} &a'(x - x_0) + b'(y - y_0)&=&0\\&a'(x - x_0)&= &b'(y_0 - y)\end {array}$

Comme $b'$ divise le premier membre et est premier avec $a',$ d'après le théorème de Gauss, il divise $x - x_0 :$ il existe un entier $k$ tel que $x - x_0 = kb' ;$ on reporte dans la dernière équation et on obtient $y - y_0 = - ka'.$

Les solutions de l'équation initiale, quand elle admet des solutions, (c'est-à-dire quand $\textrm {pgcd} (a,b)$ divise $c),$ sont données par :

$x = x_0 c' + kb'$

$y = y_0 c' - ka'$