Pgcd

[Uniaclya]

Bonjour , dans mon cahier de mathématiques , notre prof nous a fait écrire ça :
PGCD (2724;714) ?
Méthode des différences successives pour le calcul d'un PGCD :
= PGCD (714;2010)
= PGCD (714;1296)
= PGCD (714;582)
= PGCD (582;132)
= PGCD (132;450)
= PGCD (132;318)
= PGCD (132;186)
= PGCD (132;54)
= PGCD (54;78)
= PGCD (54;24)
= PGCD (24;30)
= PGCD (24;6)

Méthode des divisions successives (algorithme d'Euclide)
PGCD (2724;714) ?
2724 = 714x3+582
714= 582x1+132
582= 132x4+54
132= 54x2+24
54 = 24x2+6
24= 6x4+0
PGCD (2724;714) =6

Je suis un peu perdue , je sais ce qu'est un PGCD mais j'ai pas très bien compris comment on a procédé pour le trouver dans les deux cas , et pourquoi on continue à développer les nombres sans cesse alors qu'on arrive déjà au reste de la division euclidienne.. Je sais pas si ma question est claire mais en bref je n'ai pas du tout compris ces méthodes et j'aimerais que quelqu'un m'aide à voir ça plus claire.. Merci d'avance.

[yoruichisama]

va sur ce site en cliquant sur le lien tout y est bien expliquer :lol3:
PGCD algorithme d'euclide

[jlb]

Bonjour , dans mon cahier de mathématiques , notre prof nous a fait écrire ça :
PGCD (2724;714) ?
Méthode des différences successives pour le calcul d'un PGCD :
= PGCD (714;2010)
= PGCD (714;1296)
= PGCD (714;582)
= PGCD (582;132)
= PGCD (132;450)
= PGCD (132;318)
= PGCD (132;186)
= PGCD (132;54)
= PGCD (54;78)
= PGCD (54;24)
= PGCD (24;30)
= PGCD (24;6)

Méthode des divisions successives (algorithme d'Euclide)
PGCD (2724;714) ?
2724 = 714x3+582
714= 582x1+132
582= 132x4+54
132= 54x2+24
54 = 24x2+6
24= 6x4+0
PGCD (2724;714) =6

Je suis un peu perdue , je sais ce qu'est un PGCD mais j'ai pas très bien compris comment on a procédé pour le trouver dans les deux cas , et pourquoi on continue à développer les nombres sans cesse alors qu'on arrive déjà au reste de la division euclidienne.. Je sais pas si ma question est claire mais en bref je n'ai pas du tout compris ces méthodes et j'aimerais que quelqu'un m'aide à voir ça plus claire.. Merci d'avance.

un diviseur de a et b va diviser a-b: c'est la propriété utilisée pour la première méthode

un diviseur de a et b va diviser b et r où a=qb+r: c'est la propriété utilisée pour la deuxième méthode

on applique cela: première méthode: pgcd(2724,714)=pgcd((2724-714,714)=pgcd(2710,714) on trouve le même pgcd à partir de nombres plus petits, en recommençant le procédé le pgcd de change pas et tes nombres deviennent plus petits... jusqu'à obtenir un résultat évident pgcd(24,6)=6!!

deuxième méthode 2724=3*714+582 donc pgcd(2724,714) = pgcd(714,582) on trouve le même pgcdà partir de deux nombres plus petits, en recommençant le procédé le pgcd ne change pas et tes nombres deviennent plus petits...jusqu'à obtenir un résultat évident pgcd(6,0)=6!!


Ce sont deux méthodes ( la deuxième est souvent beaucoup plus rapide et la première est plus simple) pour obtenir le pgcd.

[Uniaclya]

Merci à vous , vos réponses m'ont aider à mieux comprendre :)