explication lemme d'euclide

[invite4a1f48b0]

bonjour je suis en terminale S spécialité maths
demain j'ai devoir surveillé sur tout ce qui concerne le pgcd mais certaines parties du chapitre me posent problème comme lemme d'Euclide pouvez vous me réexpliquer? merci beaucoup
-----

[invitea250c65c]

Salut !

Apparemment il y a plusieurs propositions qu'on appelle lemme d'Euclide, j'espère que j'ai choisi la bonne :
le lemme d'Euclide te dit que si a=bq+r est la division euclidienne de a par b (avec biensur a et b entiers) alors PGCD(a;b)=PGCD(b;r).
En gros que tu prennes le PGCD de a et b ou bien celui de b et r, ca revient au même, et tant qu'à faire, comme r<b (c'est un reste) et qu'on a choisit de préférence b<a, il te sera plus facile de calculer PGCD(b;r) que PGCD(a;b). Si tu n'y arrives toujours pas, tu considères à nouveau la division euclidienne de b par r cette fois ci (a s'est "transformé" en b et b en r) de reste r', tu peux alors écrire PGCD(b;r)=PGCD(r;r') puis ca ne marche pas, tu refais la dision de r par r' de reste r'' ... c'est l'algorithme d'Euclide. Evidemment, comme les restes diminuent au cours des itérations, ca va être de plus en plus facile de calculer le PGCD de tête, puis si tu veux pas te tromper, tu continues jusqu'à obtenir un reste nul, le PGCD est le dernier reste non nul : en effet, supposons que tu aies r'''=0, tu as PGCD(a;b)=PGCD(b;r)=PGCD(r;r') =PGCD(r';r'')=PGCD(r'';r'''=0) or PGCD(n'importe quoi ; 0)= n'importe quoi donc c'est r'', de manière générale le dernier reste non nul.

En fait quand tu y réfléchis, tout ca c'est la même chose que les divisions successives qu'on nous faisait faire en 3eme pour trouver le PGCD.

Pour finir petite démo sur le lemme d'Euclide (tu dois l'avoir dans ton cours mais bon peut-être que dit d'une autre facon ca ira mieux) : soit d=PGCD(a;b). Par définition, d divise a et b. Or n'importe quel diviseur commun à a et b divise r=a-bq. les diviseurs communs à a et b sont donc les diviseurs communs à b et r, en particulier le plus grand de ces diviseurs, c'est à dire le PGCD de a et b. Conclusion : PGCD(a;b)=PGCD(b;r).

Voila, j'espère que j'ai dit ca de manière différente de ton cours et que tu as mieux compris.

A+++