Pgcd

par **ewok31** » 01 Fév 2012, 15:17

Bonjour je me demandais si il existait une méthode plus rapide que celle apprise en 3° pour trouver le PGCD de deux nombres...

La méthode que j'ai apprise et celle ci par exemple pour le PGCD de 935 et 385:

PGCD(935;385) = PGCD(385;165) = PGCD(165;55)=55.
935=385*2+165 385=165*2+55 165=3*55+0
Je m'arrête quand le reste est égale à 0.

Le problème pour cette méthode est qu'elle peut être très longue...
Je sais qu'il y a plusieurs méthodes mais laquelle est la plus efficace? :mur:

par **Jota Be** » 01 Fév 2012, 15:58

ewok31 a écrit:Bonjour je me demandais si il existait une méthode plus rapide que celle apprise en 3° pour trouver le PGCD de deux nombres...

La méthode que j'ai apprise et celle ci par exemple pour le PGCD de 935 et 385:

PGCD(935;385) = PGCD(385;165) = PGCD(165;55)=55.
935=385*2+165 385=165*2+55 165=3*55+0
Je m'arrête quand le reste est égale à 0.

Le problème pour cette méthode est qu'elle peut être très longue...
Je sais qu'il y a plusieurs méthodes mais laquelle est la plus efficace? :mur:

Bonjour,
Cette méthode est la bonne et n'est pas longue.
Si tu veux, une autre méthode est accessible : la décomposition de chaque nombre en facteurs premiers.
Ainsi, 935=5*11*17 et 385=5*7*11
PGCD(935;385) est le produit des facteurs communs à 935 et 385 visibles dans leur décomposition, soit 5*11=55.
Ca te fera au moins un peu de culture

par **herve67** » 01 Fév 2012, 16:15

Il y en a une qui est sympas, MAIS AU COLLEGE VOUS DEVEZ APPLIQUER CELLE DU PROFESSEUR

Je la met tout de même, c'est la méthode par soustraction soit :
PGCD(935;385)
=PGCD(935-385 ; 385) = pgcd(550;385)
=pgcd(385;550-385) = pgcd (385;165)
=pgcd(220;165)
=pgcd(165;55)
=pgcd(110;55)
=pgcd(55;55)
=pgcd(55;0) soit 55 est le pgcd

par **ewok31** » 01 Fév 2012, 16:29

Ok merci beaucoup il y a donc 3 techniques?

par **herve67** » 01 Fév 2012, 16:36

ewok31 a écrit:Ok merci beaucoup il y a donc 3 techniques?

A ma connaissance oui :zen:

par **chan79** » 04 Fév 2012, 14:26

Bonjour
Tout à fait d'accord avec ce qui a été dit
Je rajoute qu'avant de se lancer dans une méthode, il faut prendre le temps de regarder les nombres
Par exemple, si on demande le PGCD de 41 et 26, c'est forcément 1 puisque 41 est premier et supérieur à 26 (bien-sûr, il faut savoir que 41 est premier)

par **nodjim** » 04 Fév 2012, 18:07

La méthode par soustraction n'est pas très pratique pour trouver le PGCD de 2 nombres de valeurs très différentes, par exemple 32666268469870 et 47.
ça risque d'être un peu longuet...

Pgcd

Pgcd

Qui est en ligne