Bonjour
l'algorithme d'Euclide sert à déterminer un pgcd
il repose sur la propriété de ton topic précédent

Bonjour.

Cet algorithme nous permet de calculer des PGCD.

En fait, il vient de ce résultat.

Si a=bq+r alors pbd(a,b)=pgcd(b,r)

Ainsi, lorsque l'on doit calculer le pgcd de deux nombres, on effectue la division de l'un par l'autre, et on calcul le pgcd du diviseur et de son reste et ainsi de suite.

Par exemple on veut calculer PGCD(325,30)

On voit que 325=10*30+25

On a donc PGCD(325,30)=PGCD(30,25)

Or : 30=1*25+5 donc PGCD(30,25)=PGCD(25,5)

Pas besoin de continuer, le PGCD est direct, il vaut 5 (puisque 5 n'a que deux diviseurs : 1 et lui même et 25 est divisible par 5)

Tu vois le principe?

merci

oui j'avais compris la méthode de calcul mais là tu n'as pas utilisé l'algorithme ? parce que en fait mon premier problème viens de la suite définie.

je parle de cette propriété:

Ben si c'est exactement ce que j'ai fait.

oui mais alors pourquoi la suite est définie: je ne vois pas le rapport....

et r_1 est le reste de a par b.

mais il représente le reste de quelle division ?

r_n est le reste de la division de r_n-2 par r_n-1

en fait a=b*q_1+r_1

b=r1*q_2+r_2

puis r_1=r_2*q_3+r_3

donc r_n=r_(n+1)*q_(n+2)+r_(n+2)

et on peut trouver un entier r_(n+2) tel que r_(n+2)=0

donc PGCD(r_n;r_(n+1))=q_(n+2)

est ce que c'est ca ?

merci pour ta patience...