ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

Résolution de l'équation ax + by = c         » utiliser le programme on line

On se propose de résoudre en nombres entiers l'équation d'inconnue (x,y), élément de Z² de la forme ax + by = c où a, b et c sont donnés dans Z, a et b non nuls.

Un critère fondamental de reconnaissance d'entiers naturels premiers entre eux, appelé identité de Bezout, (on devrait lire et écrire Bézout et  même identité de Bachet...) peut s'énoncer ainsi :

Théorème :    

Pour que deux entiers naturels a et b soient premiers entre eux, il faut et il suffit que l'on puisse trouver
deux entiers relatifs u et v tels que au + bv = 1     (bzt)

Prouvons ce résultat car la démarche utilisée conduira à l'algorithme informatique résolvant l'équation : dire que a et b sont premiers entre eux, c'est dire que leur seul diviseur commun est 1. C'est donc dire que leur pgcd est 1. Nous écrivons : a ^ b = 1.

La condition (bzt) est suffisante :                 

Soit d un candidat se prétendant diviseur commun de a et b; il divise donc au et bv, donc aussi la somme au + bv et par suite il divise 1. Donc d = 1 et a et b sont premiers entre eux.

La condition (bzt) est nécessaire :                

Pour les spécialistes des sous groupes additifs de Z, notés nZ, l'identité de Bézout peut se démontrer très simplement lorsque l'on sait que si d désigne a ^ b, on a : dZ = aZ + bZ. Il est cependant préférable de présenter une démonstration plus élémentaire, très bien adaptée à la programmation sur ordinateur :

♦  Supposons tout d'abord a et b premiers entre eux avec a > b. Considérons les divisions euclidiennes successives de n.a par b lorsque n est élément de {1, 2, 3, ... , b - 1} :

i/ Chaque reste est au plus égal à b - 1 et aucun de ces restes ne peut égaler 0, sinon b diviserait un des produits n.a et comme b est premier avec a, b diviserait n : ce qui serait absurde puisque n < b.

ii/ Si u et v sont deux valeurs distinctes de n, les restes r et r' obtenus sont distincts. En effet, posons au = bq + r et av = bq' + r' avec u > v. Si r = r', on a : a(u - v) = b(q - q'); par suite b divise u - v. Mais u et v sont non nuls et ne peuvent excéder b - 1; par conséquent u - v n'excède pas b - 2 et b ne peut donc pas diviser u - v. Conclusion : r et r' sont distincts.

 ➔   On peut aussi choisir pour u la valeur de n pour laquelle le reste est b - 1; on a alors : au = bq + (b-1) = b(q+1) - 1 et l'identité de Bézout est établie en écrivant a(-u) + b(q+1) = 1.

♦  Lorsque a et b ne sont pas premiers entre eux, posons d = a ^ b, pgcd de a et b. La somme ax + by est divisible par d et par conséquent, si c n'est pas multiple de d, l'équation (e) ne possède pas de solutions, sinon on se ramène au cas a ^ b = 1 en divisant par d.

Ainsi, dans toute la suite, on peut supposer a ^ b = 1.

Résolution de l'équation ax + by = c :              

Appelons (e) cette équation ax + by = c. Lorsque (bzt) est résolue, on a l'égalité au + bv = 1 , par suite a.(uc) + b.(vc) = c et le couple (x_o,y_o) = (uc,vc) est une solution de (e). Supposons donc connue une solution (x_o,y_o). Nous pouvons écrire que (e) équivaut au système :

ax + by = c
ax_o + by_o = c

Posons : X = x - x_o et Y = y - y_o

Le système est équivalent à :

aX + bY = 0
ax_o + by_o = c

Or aX + bY = 0 équivaut à : aX = -bY, et cela signifie que a divise bY et que b divise aX. Mais il a été supposé que a et b sont premiers entre eux; par suite a divise Y, donc Y = ak (k entier relatif), d'où X = - bk et les solutions de (e) sont de la forme :

(x_o - bk , y_o + ak), k décrivant Z.

Tester le programme de résolution (JavaScript) : » 

∗∗∗  Exercices

1. Résoudre en nombres entiers : 24x - 18y = 154
2. Résoudre en nombres entiers : 13x + 15y = 3.
3.  Résoudre dans N² : 24x - 18y = 156.

@ Vérifiez vos solutions au moyen de ce programme JavaScript ou bien :
Si vous séchez après avoir bien cherché : »

1.  4x - 18y = 154.

On voit immédiatement en simplifiant par 2 que cette équation n'a pas de solutions car 77 n'est pas un multiple de 3.

2.  13x + 15y = 3.

Les entiers 13 et 15 sont premiers entre eux. L'équation est donc résoluble. 15 = 13 × 1 + 2, par suite 15 × 6 = 13 × 6 + 12 = 13 × 7 - 1. On en déduit que 13 × 7 - 15 × 6 = 1 : une solution particulière est donc (x_o,y_o) = (21,-18). D'où la solution générale dans Z² :

(x,y) = (21 - 15k , 13k - 18), k décrivant Z

3.  24x - 18y = 156, x et y positifs.

Résolvons tout d'abord dans Z². On a pgcd(24;18) = 6 et 156 est divisible par 6. On simplifie par 6; l'équation se ramène alors à 4x - 3y = 26. Or 4 × 1 - 3 × 1 = 1, donc (x_o,y_o) = (26,26) est une solution particulière de l'équation.

D'où la solution générale dans Z² : (x,y) = (26 + 3k , 26 + 4k), k décrivant Z

• 26 + 3k ≥ 0  et  26 + 4k ≥ 0  ⇔  k ≥ - 8  et  k ≥ - 6  ⇔  k ≥ - 6. D'où la solution générale dans N² :

 (x,y) = (26 + 3k , 26 + 4k), k ∈ {-6, -5, -4, -3, -2, -1, 0} ∪ N

---

Problème de l'auberge d'Euler :  »