É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'\)