Inscription / Connexion Nouveau Sujet
Niveau seconde
Partager :

Calculer le PGCD de 2 nombres avec l Algorithme d Euclide

Posté par gawaz (invité) 02-11-05 à 14:45

Bonjour à tous !

Voilà, j'ai un exercice à faire et il nous demande de calculer le PGCD (322;112) et PGCD (118404;13884) à l'aide de l'algorithme d'Euclide... comment faire ?

Merci d'avance.

Posté par Frip44 (invité)re : Calculer le PGCD de 2 nombres avec l Algorithme d Euclide 02-11-05 à 14:50

Bonjour gawaz...

322=112\times 2+98
112=98\times +\fbox{14}
98=14\times 7+0
14 est le dernier reste non nul, donc 14 est le PGCD(322;112)

Essaye de faire l'autre maintenant

++
(^_^(Fripounet)^_^)

Posté par gawaz (invité)re : Calculer le PGCD de 2 nombres avec l Algorithme d Euclide 02-11-05 à 14:51

Mais je ne comprends pas d'où vient les nombres 98 et 14, il s'agit des restes ?

Posté par diamant592 (invité)re : Calculer le PGCD de 2 nombres avec l Algorithme d Euclide 02-11-05 à 14:57

oui mais ça ce n'est pas l'algorithme d'euclide

Posté par Frip44 (invité)re : Calculer le PGCD de 2 nombres avec l Algorithme d Euclide 02-11-05 à 14:57

Re gawaz...

On part de : a=b_0\times q_0 +r_0 (en passant les détails du genre 0\le r_0<b)
On fait ensuite b_0=r_0\times q_1+r_1
Puis, r_0=r_1\times q_2+r_2
Puis, r_1=r_2\times q_3+r_3
Et ce jusqu'à ce que dans, r_{n-2}=r_{n-1}\times q_n+r_n, r_n=0 et dans ce cas, r_n=PGCD(a,b)

Sauf étourderie...

++
(^_^(Fripounet)^_^)

Posté par Frip44 (invité)re : Calculer le PGCD de 2 nombres avec l Algorithme d Euclide 02-11-05 à 14:57

Dans ce cas diamant592, qu'est ce que l'algorithme d'euclide selon toi ?

Posté par diamant592 (invité)re : Calculer le PGCD de 2 nombres avec l Algorithme d Euclide 02-11-05 à 14:59

J'ai rien dit........

Posté par Frip44 (invité)re : Calculer le PGCD de 2 nombres avec l Algorithme d Euclide 02-11-05 à 15:02

Oups, lorsque r_n=0, r_{n-1}=PGCD(a,b), autant pour moi

Posté par gawaz (invité)re : Calculer le PGCD de 2 nombres avec l Algorithme d Euclide 02-11-05 à 15:22

Pour commencer, j'ai trouvé ça :

118404= 13884 x 8 + 7332
13884= 7332 + 6552
... et après je ne sais pas comment faire ??

Posté par gawaz (invité)re : Calculer le PGCD de 2 nombres avec l Algorithme d Euclide 02-11-05 à 16:01

C'est bon j'ai compris MERCI !



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1489 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !