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 Z2 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 :

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 :

a.u + b.v = 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 a.u et b.v, donc aussi la somme a.u + b.v 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 u.a = b.q + r et v.a = b.q' + r' avec u > v. Si r = r', on a (u - v).a = 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.

iii/ Puisque tous les restes des divisions successives sont distincts et non nuls, nous en avons donc b - 1 distincts. Les restes constituent donc l'ensemble {1, 2, 3, ... , b-1}. Soit u la valeur de n pour laquelle le reste est 1, et q le quotient de u.a par b, on a : u.a = b.q +1 et l'identité de Bézout est établie avec v = -q.

  Noter que l'on peut aussi choisir pour u la valeur de n pour laquelle le reste est b - 1; on a alors : u.a = b.q + (b-1) = b(q+1) - 1 et l'identité de Bézout est établie en écrivant (-u).a + 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 (xo,yo) = (uc,vc) est une solution de (e). Supposons donc connue une solution (xo,yo). Nous pouvons écrire que (e) équivaut au système :

ax + by = c
axo + byo = c

Posons X= x - xo et Y=y - yo, le système est équivalent à :

aX + bY = 0
axo + byo = 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 :

(xo - bk , yo + 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 N2 : 24x - 18y = 156.

Vous pouvez vérifier vos solutions au moyen de  ce programme de résolution :  mais... :
Si vous séchez après avoir bien cherché :

 4.  Problème de l'auberge d'Euler


© Serge Mehl - www.chronomath.com

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Solution :

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 x 1 + 2, par suite 15 x 6 = 13 x 6 + 12 = 13 x 7 - 1. On en déduit que 13 x 7 - 15 x 6 = 1 : une solution particulière est donc (xo,yo) = (21,-18). D'où la solution générale dans Z2 :

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

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

Résolvons tout d'abord dans Z2. 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 (xo,yo) = (26,26) est une solution particulière de l'équation.

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

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


© Serge Mehl - www.chronomath.com