Le plus grand diviseur commun de deux entiers

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

Le plus grand diviseur commun

Premier entier

Second entier

Calculer

PGCD

 

 Lien  sauvegarder  Widget