Algorithme euclidien (PGCD)

Calculez le plus grand diviseur commun (PGCD) de deux nombres à l'aide de l'algorithme euclidien étape par étape.

Nombres

Numéro A

Numéro B

Analyse PGCD

Plus grand diviseur commun

Multiple le moins commun23562

Ratio simplifié51 : 22

Iterative Process

1.1071=(2 × 462)+147

2.462=(3 × 147)+21

3.147=(7 × 21)+0Done!

L'algorithme euclidien

L'algorithme euclidien est une méthode efficace pour calculer le plus grand commun diviseur (PGCD) de deux entiers. Il repose sur le principe selon lequel le PGCD de deux nombres divise également leur différence. Plus précisément, GCD(a, b) = GCD(b, a mod b). Répéter cette opération jusqu'à ce que le reste soit nul révèle le GCD.

💡

Pro Tips

Le PGCD de deux nombres quelconques est toujours au moins 1.
Si le PGCD est 1, les nombres sont dits « premiers entre eux » ou « relativement premiers ».
L'algorithme est utilisé dans la cryptographie moderne, notamment dans l'algorithme de chiffrement RSA.

Fun Facts

"L'algorithme d'Euclide est l'un des algorithmes numériques les plus anciens encore utilisés couramment, apparaissant dans les « Éléments » d'Euclide vers 300 avant JC."
"L'algorithme peut être visualisé en recouvrant un rectangle de carrés."
"Le théorème de Lamé stipule que le nombre d'étapes de l'algorithme est au plus égal à 5 fois le nombre de chiffres du plus petit nombre."

Formula: une = q * b + r

Used with this

Similar tools that might be useful

Convertisseur de formes de nombres complexes

Convertissez entre les formes rectangulaires (a + bi) et polaires (r∠θ) de nombres complexes.

Calculateur de triangles AAA

Analysez la proportionnalité et la similarité des triangles lorsque les trois angles sont connus.

Calculateur de triangle AAS

Résolvez un triangle lorsque deux angles et un côté non inclus sont connus.