Theoreme de Bezout.

[invite553243dd]

Bonjour tout le monde!
Bon, un projet : Faire un programme sur ma TI-83 qui resoud tout equations du genre ax+by=c (a b et c appartenant a Z)
Mon programme marche, mais j'aimerai savoir si il y avait une autre maniere de le faire.
Mon programme en ce moment


1. Si b inferieur a 0, -b = b et z = -1 (z = 1 au debut du programme, c'est une variable qui intervient plus tard sachant que gcd(a,b) marche seulement pour a et b positifs)

2. Verification que PGCD(a,b) est un multiple de c si non aucune solution.

3. Algorithme d'euclide.
a = b x b' + c
b = c x c' + d
c = d x d' + e
d = e x e' + f
f = f x f' + g... etc, jusqua ce que le reste soit egale a gcd(a,b)

la maniere dont je l'ai traduite dans mon programme est

b ' = int(a/b)
c = a - b x b'
puis b devient a, c devient b, et b' est rangé dans une liste, et ca recommence.

apres dans l'etude du cas general que j'ai fait sur papier.
a = b x b' + c
b = c x c' + d
c = d x d' + e
d = e x e' + f
e = f x f' + gcd(a,b)
en remontant on trouve

gcd (a,b) = e - f x f'
gcd (a,b) = e - (d - e x e') x f'
gcd (a,b) = e (1 + e'f') - d x f'
gcd (a,b) = (c - d x d')(1+e'f') - d x f'
gcd (a,b) = c (1 + e'f') - d (f' + d' + d'e'f')
gcd (a,b) = c (1 + e'f') - (b - c x c')(f' + d' + d'e'f')
gcd (a,b) = c (1 + e'f' + c'f' + c'd' + c'd'e'f') - b (f' + d' + d'e'f')
gcd (a,b) = (a-b x b')(1 + e'f' + c'f' + c'd' + c'd'e'f') - b (f' + d' + d'e'f')
gcd (a,b) = a (1 + e'f' + c'f' + c'd' + c'd'e'f') - b )(f' + d' + d'e'f' + b' + b'e'f' + b'c'f' + b'c'd' + b'c'd'e'f')

N'y a t'il pas plus simple? Enfin, apres j'ai remarqué que on pouvait traduire ca par (a est le multiple du premier nombre, b est le multiple du second, quel que soit le nombre)

a = 1
b = f'
a = a + e'b
b = b + d'a
a = a + c'b
b = b + b'a

ou la lettre avec le ' remonte d'une lettre a chaque fois, et le a ou b dans la seconde partie de l'egalité fait reference au a ou b avant lui. on remonte jusqua ce que la liste ou etait ranger tout les nombres avec les ' soit epuisée, et on a notre solution. Apres on arrange la solution pour avoir des choses dans le genre y = ak+b et x = a'k + b' mais ca c'est moins compliqué.
Je voudrai savoir si il n'y a pas de methode plus rapide/simple que celle que j'ai trouvé? (Je ss en terminale, specialité maths)
-----

[inviteeecca5b6]

jusqua ce que le reste soit egale a gcd(a,b)

Si ma mémoire est bonne, il faut arréter l'algorithme quand le reste = 0 et a ce moment le PGCD est le dernier diviseur...
De plus, je pinaille mais c'est pour rendre ton programme robuste, il faut s'assurer que a>b !
Mais bon, en mon temps j'avais fait cet algo sur casio et il allait bien...
Ensuite les couples solutions te sont donnés par:
ax + by = c
a/c x + b/c y = 1
k1 x + k2 y = 1
x = (1 - k2 y) / k1
Avec int((1 - k2 y) / k1) - (1 - k2 y) / k1 = 0
Et la ca te donne une liste de nombre...

[invite3f53d719]

L'algorithme le plus efficace pour trouver les coefficients de Bezout est celui ci:

BEZOUT(a,b)
(x,y)<-(a,b);
(u0,v0)<-(1,0);
(u1,v1)<-(0,1);
Tant_que y<>0 faire
    q<-quotient de x par y;
    (x,y)<-(y,x-q*y);
    (u0,u1)<-(u1,u0-q*u1);
    (v0,v1)<-(v1,v0-q*v1);
Fait; (u0,v0);

Il provient directement de la démonstation par récurrence du théorème, qui n'est pas très compliqué à faire.

[invite553243dd]

Non, a n'est pas forcement superieur a b, par exemple

a = 20
b = 30

20 = 30 x 0 + 20
30 = 20 x 1 + 10
20 = 10 x 2 + 0

Ca fait un pas en plus au debut mais tout tombe juste, et pour l'algorithme d'euclide oui, normalement il faut aller juqu'a 0, mais le pas de 0 nous permet de savoir que le reste du dernier pas c'etait le pgcd, mais comme on connait le pgcd d'avance grace a la fonctoin gcd(a,b) on peux s'arreter en avance
Merci beaucoup pour les algorithmes!

[A voir en vidéo sur Futura]

[inviteeecca5b6]

Non, a n'est pas forcement superieur a b, par exemple

a = 20
b = 30

20 = 30 x 0 + 20
30 = 20 x 1 + 10
20 = 10 x 2 + 0

Ca fait un pas en plus au debut mais tout tombe juste, et pour l'algorithme d'euclide oui, normalement il faut aller juqu'a 0, mais le pas de 0 nous permet de savoir que le reste du dernier pas c'etait le pgcd, mais comme on connait le pgcd d'avance grace a la fonctoin gcd(a,b) on peux s'arreter en avance
Merci beaucoup pour les algorithmes!

C'est juste...
Ca remonte a bien vieux tout ca pour moi...