Répondre à la discussion
Affichage des résultats 1 à 5 sur 5

Theoreme de Bezout.



  1. #1
    siris

    Theoreme de Bezout.


    ------

    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)

    -----

  2. Publicité
  3. #2
    Evil.Saien

    Re : Theoreme de Bezout.

    Citation Envoyé par siris
    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...
    Mon psychiatre, pour quinze mille francs, il m'a débarrassé de ce que j'avais : quinze mille francs

  4. #3
    Eric78

    Re : Theoreme de Bezout.

    L'algorithme le plus efficace pour trouver les coefficients de Bezout est celui ci:
    Code:
    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.
    Pour un TPE sur la cryptographie ou les trous noirs, allez voir mon profil.

  5. #4
    siris

    Re : Theoreme de Bezout.

    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!

  6. A voir en vidéo sur Futura
  7. #5
    Evil.Saien

    Re : Theoreme de Bezout.

    Citation Envoyé par siris
    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...
    Mon psychiatre, pour quinze mille francs, il m'a débarrassé de ce que j'avais : quinze mille francs

Discussions similaires

  1. Identité de Bézout et PGCD
    Par bastien90210 dans le forum Mathématiques du collège et du lycée
    Réponses: 12
    Dernier message: 08/12/2007, 11h36
  2. méthodes de Cardan, Sotta et Bézout = ???
    Par titi9 dans le forum Mathématiques du collège et du lycée
    Réponses: 11
    Dernier message: 08/11/2006, 14h03
  3. theoreme de Bezout
    Par Kelm dans le forum Mathématiques du collège et du lycée
    Réponses: 8
    Dernier message: 07/06/2006, 09h28
  4. arithmétique: théorème de bezout
    Par mag dans le forum Mathématiques du collège et du lycée
    Réponses: 1
    Dernier message: 01/04/2006, 13h19
  5. Egalité de Bézout
    Par prgasp77 dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 14/11/2004, 17h38