Equation de Diophante ax + by = c

Le libraire
On obtient immédiatement une équation 97x + 29y = 4000 (les prix en centimes).
Donnons ici simplement le résultat fondamental pour ce type d'équation :

L'équation ax + by = c est soluble si et seulement si p = PGCD(a,b) divise c En posant alors a = pa', b = pb' c = pc', si x0,y0 est une solution particulière de  a'x + b'y = 1, alors toutes les solutions de ax + by = c sont données par :      x = c'x0 - kb'     y = c'y0 + ka' où k parcourt Z

Le problème est de trouver une solution particulière.
Si on peut dans les cas simples opérer par tâtonnements, une équation comme 97x + 29y = 4000 nécessite une méthode plus efficace.
Une méthode possible est l'algorithme d'Euclide "étendu" :
("étendu" car calculant en plus les P et Q)

Posons : r0 = a, r1 = b (a > b > 0) P0 = 0, P1 = 1 et Q0 = 1, Q1 = 0 Puis répéter depuis i = 2     - Division entière de ri-2 par ri-1 : ri-2 = ri-1qi + ri      - Calculer Pi = -qiPi-1 + Pi-2 et Qi = -qiQi-1 + Qi-2      - jusqu'à rn = 0 p = rn-1 est le PGCD de a et b (algorithme d'Euclide)  En posant a' = a/p et b' = b/p, x0 = Qn-1, y0 = Pn-1 est solution de a'x + b'y = 1

On peut au besoin se ramener à a > b > 0 par changement de variables (échanges de x et y et cahngement de signes).

Connaissant une solution de ax + by = 1, on obtient une solution de ax + by = c en multipliant x et y par c.

Avec 97x + 29y = 4000 cela donne :
97 = 29×3 + 10, r₂ = 10, q₂ = 3, P₂ = -3, Q₂ = 1
29 = 10×2 + 9, r₃ = 9, q₃ = 2, P₃ = 7, Q₃ = -2
10 = 9×1 + 1, r₄ = 1, q₄ = 1, P₄ = -10, Q₄ = 3
9 = 1×9 + 0, r₅ = 0, c'est fini et x = 3 y = -10 est solution de 97x + 29y = 1
En multipliant par c = 4000, qui est bien un multiple de p = r₄ = 1, on obtient x = 12000 + 29k, y = -40000 - 97k
Qui n'est pas la valeur la plus simple !

Mais si on pose m = k + [12000/29] = k + 413, on trouve :

 x = 23 + 29m, y = 61 - 97m .

Script de résolution de ax + by = c avec cet algorithme.

Une étude plus détaillée de l'équation de Diophante.

En particulier une méthode plus "intuitive", mais plus lourde à appliquer, de changements de variables. Ceci revient dans les faits à l'algorithme d'Euclide, mais sans l'aspect "parachuté" ci dessus (ou démonstration théorique de sa validité).
Le principe :
97x + 29y = 4000 s'écrit 10x + 29(y + 3x - 137) = 27 soit en posant z = y + 3x - 137 : 10x + 29z = 27.
On poursuit ainsi de proche en proche par changements de variables successifs jusqu'à l'équation triviale t + 9u = 7 qui possède la solution évidente t = 7, u = 0. On remonte ensuite tous les changements de variables pour obtenir x et y.

Equations à plus de 2 inconnues

La pile de livres donne 15x + 21y + 35z = 200 (en mm).
Pour résoudre une telle équation, il suffit de considérer toutes les inconnues sauf deux comme des paramètres et de les faire passer dans le second membre.
Ce qui donne : 15x + 21y = 200 - 35z = c et on est amené à résoudre 15x + 21y = c en fonction de c.
Petit problème bien sûr car 15 et 21 ne sont pas premiers entre eux. c doit donc être un multiple du PGCD 3 de 15 et 21.
C'est à dire que 200 - 35z ≡ 0 mod (3) ou encore z ≡ 1 mod(3). Ce qui s'écrit z = 3m + 1. La véritable inconnue est m et non pas z.
Notre équation s'écrit 15x + 21y = 165 - 3×35m et en divisant tout par 3 : 5x + 7y = 55 - 35m.
Comme x₀ = 3, y₀ = -2 est solution de 5x + 7y = 1 (exercice de révision...), la solution générale de cette équation s'écrit
x = 3(55 - 35m) + 7k, y = -2(55 - 35m) - 5k et finalement

x = 165 - 105m - 7k y = -110 + 70m + 5k z = 3m + 1 k et m parcourant indépendamment Z

La contrainte x,y,z > 0 donne z > 0 donc m > -1/3 soit m ≥ 0
x,y > 0 soit x,y ≥ 1, et 35z ≤ 200 - 15 - 21, soit z ≤ 164/35, soit z ≤ 4 et donc m ≤ 1, et finalement 0 ≤ m ≤ 1.
Pour m = 0, x = 165 - 7k > 0 et y = -110 + 5k > 0 donnent 110/5 < k < 165/7 soit 22 < k ≤ 23 donc k = 23.
Pour m = 1 x = 60 - 7k, y = -40 + 5k soit 40/5 < k < 60/7 et 8 < k≤ 8 ce qui est impossible.
Il y a donc une seule solution : m = 0, k = 23, qui donne x = 4, y = 5, z = 1.