Salut !

En fait c'est l'algorythme d'Euclide.
Je t'explique la methode de facon generale et je l'applique a l'exemple que tu as donne...

En fait pour calculer le pgcd de deux entiers a et b, on utilise la division euclidienne et le fait que la suite de divisions :
a = bq_{[/sub]1+r[sub]}1 avc 0r_{[/sub]1< b
b = r[sub]}1 q_{[/sub]2+r[sub]}2 avc 0r_{[/sub]2<r[sub]}1
...
r_{[/sub]n=r[sub]}(n-1)q<sub>[/sub]n

est finie. on peut montrer que pgcd de a et b est egal au pgcd de b et r[sub]</sub>1 et ... egal au pgcd de r_{[/sub](n-1) et de r[sub]}n

Ainsi le dernier reste non nul de la suite des divisions euclidiennes sera le pgcd des deux nombres de depart.
Regardons sur ton exemple :
420 = 294x1 +126
294 = 126x2 +42
126 = 42x3 +0
le dernier reste non nul est le pgcd dc ici, PGCD(420,296)=42.

Voila ! a+ et bonne reprise

(edit T_P : problème de balise corrigé)

Salut !

Je viens de voir que la suite de mon message n'est pas passee...
Je reprends alors...
A l'endroit ou il y a la croix,il faut lire 0 infegal a r2 < r1
...
Cette suite de division est finie.
r(n-1) = rn x qn (les n = indices)

Ensuite, la justification de cette methode repose sur le fait que pgcd (a,b) = pgcd (b,r1)=...=pgcd(r(n-1),rn) = rn car rn divise r(n-1). Dc le dernier reste non nul est le pgcd de a et b.

Regardons sur ton exemple :
420=296x1+126
296=126x2+42
126=42x3+0

Le dernier reste non nul est 42 dc pgcd(420,296)=42.
Il faut continuer la suite de divisions tt qu'on n'obtient pas de reste nul.

Si le debut te semble trop complique, c'est pas grave,retiens la methode de l'exemple et vois ou sont places les nombres d'une ligne a l'autre

A+ et bonne reprise !