joré besoin de votre aide je fé des annales en vue du bac et la je tombe sur un exo dont g la correction mais celle ci n'explique rien ...
donc voila le probleme
prouver que au + bv=1 avec u et v dans N
si et seulement si a et b sont premier entre eux a savoir
pgcd(a;b)=1
L'identité de Bezout répond directement à ta question, énoncé comme suit :
Donc si d=1, pgcd(a,b)=1En arithmétique, l'identité de Bézout, d'après le nom du mathématicien Étienne Bézout, est une équation diophantienne linéaire :
ax+by=d
où a et b sont deux entiers relatifs, d leur plus grand commun diviseur, x et y deux inconnues à valeurs entières.
Mais tu dois peut être le démontrer, je ne sais pas
Cordialement.
Bonsoir,
C'est toujours délicat de "démontrer" une identité de base quand on ne sais pas ce quelles sont exactement ce qui est censé être admis.
Allons y quand même :
identité => pgcd=1
Si p>1 est un diviseur de a , il divise au et donc 1-bv.
Il ne peut donc pas diviser v (car sinon, il diviserait aussi 1).
Donc aucun diviseur de a autre que 1 ne divise b, il n'ont donc que 1 comme diviseur commun.
pgcd =1 =>il existe u et v vérifiant...
C'est plus compliqué, il faut faire une récurrence sur les divisions successives du plus grand par le plus petit.
a>b => il existe q et r avec r <b vérifiant
a=bq+r et 0<r<q (r ne peut pas être égal à 0 car sinon b diviserait a)
Ensuite, on remplace a (ou b mais on descend plus vite avec a) par r et on recommence jusqu'à ce que r =1).
En remontant la chaîne, on obtient les u et v
Il faut vérifier, dans la def du pgcd et ses propirétés, si tu as le moyen d'éviter ce raisonnement fastidieux
Sinon il existe une autre version en partant du théorème de Gauss (que l'on doit donc aussi démontrer sans bezout, bien sûr !)
Bonsoir,
(il existe u et v tq au+bv=1)=>pgcd(a,b)=1 :
Bin il faut partir de la définition du pgcd, ie poser d tq
d=pgcd(a,b), dire que a=a'd, etc.
Pour l'auter sens : Utiliser l'algorithme d'Euclide.
Voila voila.
merci g pensé a ton idée bawah mais elle naboutit pas en tout cas merci pour vos reponse
je v me debrouillé ...
Si si, je t'assure que ça fonctionne !
C'est ce que t'as exposé ziniaEnvoyé par Kelm
merci g pensé a ton idée bawah mais elle naboutit pas en tout cas merci pour vos reponse
je v me debrouillé ...
Tu veux dire que tu n'aboutis pasmerci g pensé a ton idée bawah mais elle naboutit pas en tout cas merci pour vos reponse
je v me debrouillé ...
Si tu te perds dans les divisions successives, tu peux essayer par une récurrence bien posée :
Comme au+bv=(-a)(-u)+bv=au+(-b)(-v)=(-a)(-u)+(-b)(-v)
on peut choisir a et b positifs : parmi les couples (a,b) (-a,b) (a,-b) (-a,-b) il y en a toujours un formé par deux positifs
Hypothèse de récurrence pour n : pour a et b premiers entre eux avec b<=n, il existe deux entiers relatifs u et v tels que au+bv=1
Pour n=0, pgcd(a,0)=a (les diviseurs communs de a et de 0 sont les diviseurs de a, tous les nombres divisent 0) donc a=1 et a.1+b.0 convient
Supposons l'hypothèse vraie pour n>0
Soient a et b 1ers entre eux avec b<=n+1
si b<n+1 on applique l'hypothèse de récurrence,
si b=n+1, on effectue la division euclidienne :
a=bq+r avec 0<=r<b<n+1 donc r<=n
Un diviseur de b et de r divise a=bq+r
Un diviseur de b et de a divise r=a-bq
Les diviseurs communs de a et de b sont les mêmes que ceux de b et de r donc pgcd(b,r)=pgcd(a,b)=1
on peut appliquer l'hypothèse de récurrence à b et r : il existe u et v tels que bv+ru=1
et en remplaçant r par a-bq
on a bv+(a-bq)u=au+b(v-qu)=1
l'hypothèse de récurrence est donc vérifiée pour n+1. CQFD
