✖

Plus grand commun diviseur

Le plus grand commun diviseur de deux entiers est le nombre qui divise les deux nombres sans reste, et tel qu’il n’existe aucun autre nombre plus grand qui divise aussi les deux nombres sans reste.

Prenons par exemple les nombres 24 et 32. Quel est leur plus grand commun diviseur ? Nous cherchons d’abord un nombre qui divise les deux nombres.

  • Par exemple, le nombre 12 divise 24, mais ne divise pas 32, car 32 / 12 est égal à 2,666…, qui n’est pas un entier. Le nombre 12 ne peut donc pas être le plus grand commun diviseur de 24 et 32.
  • Et le nombre 4 ? Il divise les deux nombres : 24 / 4 est égal à 6 et 32 / 4 est égal à 8. Le nombre 4 est donc notre premier candidat. Existe-t-il un nombre plus grand qui divise les deux nombres ?
  • Le nombre 8 divise 24 comme 32, et il est plus grand que 4.
  • Il n’existe aucun autre nombre plus grand que 8 qui divise les deux nombres. Le nombre 8 est donc le plus grand commun diviseur de 24 et 32.

Algorithme d’Euclide pour trouver le plus grand commun diviseur

Il existe un moyen assez simple de trouver le plus grand commun diviseur de deux nombres : l’algorithme d’Euclide. Au départ, prenons deux nombres x et y dont nous voulons trouver le plus grand commun diviseur. Essayons avec les nombres x = 50 et y = 35. On procède alors ainsi :

  1. On divise x / y et on retient le reste de la division. On note ce reste z. Pour notre exemple, on obtient 50 / 35, ce qui donne un reste z = 15.
  2. On échange maintenant les variables : on met dans x la valeur de y et dans y la valeur de z. On oublie la valeur initiale de x. Après cette étape, on obtient x = 35 et y = 15.
  3. On regarde maintenant si y est égal à zéro. Si oui, le plus grand commun diviseur est le nombre x. Comme y n’est pas égal à zéro, on continue et on reprend toute la procédure depuis le premier point.
  4. On divise de nouveau x / y, c’est-à-dire 35 / 15, ce qui donne un reste z = 5.
  5. On échange les variables : on obtient x = 15 et y = 5. Comme y n’est pas égal à zéro, on continue.
  6. On divise x / y, c’est-à-dire 15 / 5. Le reste de la division est z = 0.
  7. On échange les variables et on obtient x = 5 et y = 0.
  8. À ce moment-là, y = 0 et notre algorithme s’arrête. Le plus grand commun diviseur est le nombre x = 5.

Point important : l’ordre des nombres ne joue aucun rôle. Si l’on échangeait les nombres de l’exemple, on obtiendrait le couple x = 35 et y = 50. La procédure serait la même :

  1. On divise x / y, c’est-à-dire 35 / 50, ce qui donne un reste z = 35.
  2. On échange les variables : x = 50 et y = 35.
  3. On voit qu’après cette étape, nous avons simplement échangé le contenu des variables x et y…

Calculatrice

Cette calculatrice te donne le plus grand commun diviseur.