Bonjour tony62

Méthode des soustractions

PGCD(20755;9488) = PGCD(11267;9488) --- 11267=20755-9488
PGCD(11267;9488) = PGCD(9488;1779)  --- 9488=11267-9488
PGCD(9488;1779) = PGCD(7709;1779) --- 7709=9488-1779
PGCD(7709;1779) = PGCD(5930;1779) --- 5930=7709-1779
PGCD(5930;1779) = PGCD(4151;1779)
PGCD(4151;1779) = PGCD(2372;1779)
PGCD(2372;1779) = PGCD(1779;593)
PGCD(1779;593) = PGCD(1186;593)
PGCD(1186;593) = PGCD(1186;593)
PGCD(1186;593) = PGCD(593;593)
PGCD(593;593) = 593

donc PGCD(20755;9488) = 593

@+

Zouz

Algorithme d'Euclide

Un peu de vocabulaire pour commencer:

Dividende = Diviseur * Quotient + Reste

20755 = 9488*2 + 1779

A chaque ligne:
- le dividende est le diviseur de la ligne précédente
- le diviseur est le reste de la ligne précédente

9488 = 1779*5 + 593

1779 = 593*3 + 0

Lorsque le reste est nul, le diviseur obtenu est le PGCD.

OK ?

@+

Zouz

merci pour la rapidité de ta réponse
je crois qu'il me faudra m'exercer avec plusieurs exemples pour assimiler à fond le raisonnement, mais je vais y arriver, si tu veux tu peux me donner un autre pgcd a faire pour que le fasse, merci.

Bien sûr.

Quel est le PGCD de 675 et 375 ? (appliquer les 2 méthodes)

@+

Zouz

par méthode soustraction:
pgcd(675;375)=pgcd(375;300)
pgcd(375;300)=pgcd(300;75)
pgcd(300;75)=pgcd(300;225)
pgcd(300;225)=pgcd(225;75)
pgcd(225;75)=pgcd(150;75)
pgcd(150;75)=pgcd(75;75)
pgcd(675;375)=75

mais l'autre méthode je ny arrive pas
pourrais-tu m'aider merci

Ok pour cette méthode.

Pour l'algorithme d'Euler

675 = 375 * 1 + 300
375 = 300 * 1 + 75

Tu peux faire l'étape suivante ?

Zouz

675=375x1+300
375=300x1+75
300=75x4+0
donc le pgcd(675;375)=75

merci à toi et pour ta patience en te souhaitant une bonne soirée,amicalement tony62

Impeccable. Bon courage pour la suite.

@+

Zouz