L'algorithme d'Euclide pour grands nombres, méthode de calcul pour PGCD et PPCM

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:

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):

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.

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é?

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