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

Télécharger le projet
Commenter

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.
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

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.

Du même auteur (cs_bouba)