L'algorithme d'Euclide pour de grands nombres: méthode de calcul du plus grand commun diviseur PGCD, du plus petit commun multiple PPCM

Théorie: L' algorithme Euclide: trouvez le plus grand commun diviseur (pgcd) pour de grands nombres

Pour de grands nombres, la décomposition en facteurs premiers est difficile.

Si l'on veut établir le plus grand commun diviseur (pgcd) de tels grands nombres, alors on va utiliser une méthode qui n'utilise pas la décomposition en facteurs premiers, mais on va utiliser l'algorithme d'Euclid... voir l'exemple ci-dessous.

Voyons quel est le plus grand commun diviseur (pgcd) des nombres 53.667 et 25.527:

  • 1) 53.667 = 25.527 × 2 + 2.613 (on divise le nombre le plus grand au nombre le plus petit)
  • 2) 25.527 = 2.613 × 9 + 2.010 (on divise le nombre le plus petit au reste de l'opération ci-dessus)
  • 3) 2.613 = 2.010 × 1 + 603 (on divise le reste de la première opération au reste de la deuxième opération)
  • 4) 2.010 = 603 × 3 + 201 (on divise le reste de la deuxième opération au reste de la troisième opération)
  • 5) 603 = 201 × 3 (on divise le reste de la troisième opération au reste de la quatrième opération); en ce moment, comme il n'y a plus de reste, on s'arrête, 201 est le nombre recherché.

Donc, le plus grand commun diviseur des deux nombres est le dernier reste (différent de zéro, évidemment).

Si ce dernier reste est égal avec un, alors les deux nombres sont premiers entre eux.

Pour les opérations ci-dessus, le dernier diviseur, 201 est le plus grand commun diviseur (pgcd) des nombres 53.667 et 25.527.

On peut aussi démontrer avec l'aide de l'algorithme d'Euclide le fait que deux nombres sont premiers entre eux.

Par exemple, cherchons le ppcm (87, 41):

  • 1) 87 = 41 × 2 + 5 (on divise le nombre plus grand au nombre plus petit)
  • 2) 41 = 5 × 8 + 1 (on divise le nombre plus petit au reste de l'opération ci-dessus)
  • 3) 5 = 5 × 1 (on divise le reste de la première opération au reste de la deuxième opération, mais qui est un, l'opération n'aura plus de reste)

Le dernier reste des opérations ci-dessus, pas zéro, est égal avec 1.

pgcd (87, 41) = 1, donc les nombres sont premiers entre eux.

L'application de l'algorithme d'Euclide pour plus de deux nombres:

L'algorithme d'Euclide peut être utilisé aussi pour trouver le plus grand commun diviseur (pgcd) de plusieurs nombres, par exemple a, b et c. On va procéder en étapes. Premièrement on va trouver pgcd(a, b) = d et ensuite on va trouver ppcm(c, d) = e.

Théorie: L'algorithme d'Euclide: trouvez le plus petit commun multiple (ppcm) pour de grands nombres

Au cas des grands nombres il devient incommode de calculer le plus petit commun multiple (ppcm), parce que la décomposition des facteurs premiers demande beaucoup de temps.

Avec l'aide de l'algorithme d'Euclide on trouve le plus grand commun diviseur (pgcd) - voir ci-dessus, mais aussi le plus petit commun multiple (ppcm), selon la règle:

ppcm (a, b) = (a × b) / pgcd(a, b)

Cette méthode ne peut pas s'étendre au plus de deux nombres.

Qu'est-ce qu'un nombre premier?

Qu'est-ce qu'un nombre composée?

Nombres premiers jusqu'à 1.000

Nombres premiers jusqu'à 10.000

La crible d'Ératosthène

Algorithme d' Euclide

Simplifier des fractions mathématiques ordinaires: mesures et des exemples