Le plus grand diviseur commun de deux entiers

Ce calculateur détermine le plus grand diviseur commun de deux entiers en utilisant l'algorithme d'Euclide

Le plus grand diviseur commun de deux entiers m et n est l'entier le plus grand qui les divise tous les deux.
Ce calculateur détermine le plus grand diviseur commun de deux entiers en utilisant l'algorithme d'Euclide

L'algorithme d'Euclide est très simple.
Vous commencez par construire une séquence de nombres. Le premier est le plus grand des deux entiers, le second est le plus petit des deux entiers, le troisième est le reste de la division des deux nombres précédents, le quatrième est le reste de la division du second et du troisième, etc. Le dernier reste avant zéro est la réponse.

Je vais vous montrer avec un exemple.
Supposez que nous ayons besoin du PGCD de 13 et 17.

Etape 1. Créer la séquence initiale
17, 13

Etape 2. Le troisième membre est le reste de la division de 17 par 13
17, 13, 4

Etape 3. Le quatrième membre est le reste de la division de 13 par 4
17, 13, 4, 1

Etape 4. Le cinquième membre est le reste de la division de 4 par 1
17, 13, 4, 1, 0

1 est le dernier reste avant 0, donc c'est notre réponse.
Et les nombres dont le PGCD est 1 sont appelés nombres premiers entre eux

PLANETCALC, Le plus grand diviseur commun

Le plus grand diviseur commun

PGCD
 

URL copiée dans le presse-papiers
PLANETCALC, Le plus grand diviseur commun de deux entiers

commentaires