Trouver un couple u,v (théorème de bezout) tel que au+bv=d

Soyez le premier à donner votre avis sur cette source.

Vue 7 271 fois - Téléchargée 187 fois

Description

Le programme demande deux nombres a et b, calcul le pgcd des deux nombres (d) et trouve un couple u,v tel que au+bv=d qui vérifie le théorème de Bezout.

Rappel: Théorème de Bezout
Pour tout a et b dans Z, si d=pgcd(a,b) alors il existe u et v tel que au+bv=d

Source / Exemple :


unit bezout;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Label1: TLabel;
    Label2: TLabel;
    Label3: TLabel;
    Button1: TButton;
    Button2: TButton;
    Edit1: TEdit;
    Edit2: TEdit;
    Edit3: TEdit;
    Label4: TLabel;
    Edit4: TEdit;
    Edit5: TEdit;
    Label5: TLabel;
    Label6: TLabel;
    procedure Button2Click(Sender: TObject);
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Button2Click(Sender: TObject);
var a : Integer;  {variabe pour Edit1}
    b : Integer;  {variable pour Edit2}
    r : Integer;
    d : Integer;
    u : Integer;
    v : Integer;
    temp : Integer;
begin
a := StrToInt(Edit1.Text);
b := StrToInt(Edit2.Text);

{Si les nombres sont les mêmes ou si leur division donne un nombre entier
alors il n'y a pas de pgcd}

if (a=b) or (Int(a/b) = a/b)  then
begin
Edit3.Text := 'inexistant';
temp := -1; {pour que la boucle while ne s'effectue pas (-1 a été choisi arbitrairement)}
end;

{début de la boucle while}
while (temp <> -1)  do
begin
temp := r; {Variable temporaire}

r := a mod b;   {r = reste de a par b}
a := b;
b := r;

if r = 0    {si r=0 alors le pgcd est le rest de la division précédente (c'est temp)}
then
begin
Edit3.Text := IntToStr(temp);
temp := -1;
end;

end;
{fin de la boucle while}

{recherche de u et v}
if (Edit3.Text <> 'inexistant' ) then
begin
u := 1;
d := StrToInt(Edit3.Text);   {d = pgcd(a,b)}
a := StrToInt(Edit1.Text);
b := StrToInt(Edit2.Text);

while  ( ((a*u-d) mod b) <> 0)  do   {recherche de u}
begin
u := u+1;
end;
v := (d-a*u) div b;    {v = (d-a*u)/b}
Edit4.Text := IntToStr(u);
Edit5.Text := IntToStr(v);
end;
end;

{boutton pour la fermeture du prog}
procedure TForm1.Button1Click(Sender: TObject);
begin
close
end;

end.

Conclusion :


Pour mieux comprendre comment trouver le pgcd des deux nombres allez voir ma source sur le pgcd sur ce même site, j'ai expliqué comment trouver le pgcd de deux nombres en détail.

En ce qui concerne la recherche du couple u,v voici l'explication.
Prenons un exemple simple, a=12 et b=5
on a pgcd(a,b)=1
donc d'après bezout au+bv=d ou 12u+5v=1
Le principe du programme est le suivant:
on ajoute 1 à u et on fait la division (au-d)/b ou (12u-1)/5
et on voit si la division donne un nombre entier.

prenons 1 pour u on obtient 12*1+5v=1, ou 11=-5v ce qui montre bien l'utilité de la division entière (au-d)/b

pour trouver v on fait simplement au+bv=d -> v= (d-au)/b

Voilà, c'est tout. Si vous n'avez pas bien compris n'hésitez pas à me posez une p'tite question.

Codes Sources

A voir également

Ajouter un commentaire

Commentaire

Messages postés
63
Date d'inscription
mercredi 23 janvier 2002
Statut
Membre
Dernière intervention
16 avril 2008

un petit truc ki pouré te servir:t'emmerde pas a declarer tes variables comme ca:
a : Integer;
b : Integer;
r : Integer;
d : Integer;
u : Integer;
v : Integer;
car comme ce sont des variables de meme type, ca equivaut à :
var a,b,r,d,u,v:integer {plus rapide non?}

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.