Pgcd

par **MC91** » 25 Fév 2013, 19:26

Bonjour,

Je voudrais avoir quelques précisions sur le PGCD.
Si on a d=au+bv, peut on conclure que d est le pgcd de a et b?

Merci.

par **Pianoo** » 25 Fév 2013, 19:30

En général non.

Mais si d=1 oui tu peux conclure.

En fait ça marche dans le sens suivant :
Si d est le pgcd de a et b, alors il existe u et v tels que au + bv = d.
ça ne marche pas dans l'autre sens !

Sauf si pgcd(a,b)=1, alors là c'est génial ça marche dans les deux sens.

par **MC91** » 25 Fév 2013, 19:54

Pianoo a écrit:En général non.

Mais si d=1 oui tu peux conclure.

En fait ça marche dans le sens suivant :
Si d est le pgcd de a et b, alors il existe u et v tels que au + bv = d.
ça ne marche pas dans l'autre sens !

Sauf si pgcd(a,b)=1, alors là c'est génial ça marche dans les deux sens.

D'accord, merci beaucoup !

par **leon1789** » 25 Fév 2013, 20:58

MC91 a écrit:Bonjour,

Je voudrais avoir quelques précisions sur le PGCD.
Si on a d=au+bv, peut on conclure que d est le pgcd de a et b?

Merci.

On peut en déduire que d est un multiple du pgcd de a et b. Il y a même équivalence :

soit a,b,d des entiers.
il existe u,v tels que d=au+bv si et seulement si d est multiple de pgcd a,b

par **MC91** » 26 Fév 2013, 09:48

leon1789 a écrit:On peut en déduire que d est un multiple du pgcd de a et b. Il y a même équivalence :

Ok, merci pour ces précisions !
A bientôt !
Bonne journée.

Pgcd

Pgcd

Qui est en ligne