PGCD démonstration

[henmil]

Bonjour les amis,

Je suis coincé et voulais savoir comment démontrer ces deux propositions.

1.
Démontrer que pour tout entier d>0, si y>0 alors
(d divise x et d divise y) si et seulement si (d divise y et d divise x mod y).
En déduire que si y>0, alors PGCD(x,y) = PGCD(y, x mod y).


2.
En déduire par induction généralisée sur y: Euclide(x,y) = PGCD(x,y) pour
tout entier x sous la condition que x et y ne soient pas tous deux nuls

Voici l'algorithme Euclide(x,y)

procédure Euclide(x: naturel; y: naturel): naturel;
si y=0 alors retourner x;
sinon retourner Euclide(y, x mod y);
fin si;
fin Euclide.

Merci pour votre aide

henmil
_________________
hm

[MikO]

salut,

pour la 1°

si x < y alors c'est evident, car x modulo y = x
si x > y alors x : ky+b
or d divise x, il divise donc ky+b, divisant y il divise aussi ky+b-ky=b, il divise bien x modulo y (il ya equivalence )

[henmil]

Merci pour votre aide mais et pour le
PGCD(x,y) = PGCD(y, x mod y)

[yos]

Bonjour.
Les diviseurs communs de x et de y sont les mêmes que les diviseurs communs de x mod y et de y.
(on a en effet : x mod y=x+ky)