Bonsoir
J'ai plusieurs questions
Lorsqu'on dit : au+bv=1 est-ce u et v sont nécessairement premier entre eux ou c'est juste a et b qui sont premiers entre eux ?
Dans un exercice on me demande de démontrer PGCD(a;b)=PGCD(a-b;b)
Notons d le pgcd de a-b et b; et p le pgcd de a et b.
On a au'+bv'=p
et (a-b)u+bv=d soit au+b(v-u)=d, en posons U=u et V=v-u on obtient aU+bV=d
Ainsi on a nécessairement d=p
C'est correct ?
pgcd
-
sos-math(21)
- Messages : 10401
- Enregistré le : lun. 30 août 2010 11:15
Re: pgcd
Bonjour,
L'égalité de Bezout est double :
puisque quand on considère u et v, on a \(au+bv=1\), donc u et v sont aussi premiers entre eux.
Pour le pgcd, je pense qu'on peut s'y prendre sans utiliser Bezout.
Si d=pgcd(a,b) alors d divise a et d divise b donc d divise a-b donc d est un diviseur commun a et a-b donc il divise leur pgcd.
On peut travailler dans l'autre sens en partant du pgcd de a et a-b et montrer qu'il divise le pgcd de a et b.
Voilà comment je ferais...
Bonne continuation
L'égalité de Bezout est double :
puisque quand on considère u et v, on a \(au+bv=1\), donc u et v sont aussi premiers entre eux.
Pour le pgcd, je pense qu'on peut s'y prendre sans utiliser Bezout.
Si d=pgcd(a,b) alors d divise a et d divise b donc d divise a-b donc d est un diviseur commun a et a-b donc il divise leur pgcd.
On peut travailler dans l'autre sens en partant du pgcd de a et a-b et montrer qu'il divise le pgcd de a et b.
Voilà comment je ferais...
Bonne continuation