Euclidean Algorithm GCD

Algorithme Euclidien Animé

Plus grand diviseur commun.

Utile pour réduire les fractions

Algorithme euclidien visible

GCD, également connu sous le nom de plus grand facteur commun (gcf), facteur commun le plus élevé (hcf), plus grande mesure commune (gcm), ou plus grand commun diviseur.

Représentation dynamique et géométrique de l'algorithme.

Algorithme récursif

Et le plus petit commun multiple déduit de GCD:

lcm (a, b) = a * b / gcd (a, b)

Utile pour comprendre le code récursif gcd (algorithme euclidien): (Java)

int gcd (int m, int n) {

    si (0 == n) {

        retourner m;

    }autre{

        retourne gcd (n, m% n);

    }

}

Ajout de la visualisation géométrique.

Algorithme exécuté par les pissenlits provenant du jardin mathématique voisin

Historique de l'algorithme euclidien:

("Le pulvérisateur")

L'algorithme euclidien est l'un des algorithmes les plus anciens couramment utilisés.

Il apparaît dans les Éléments d'Euclide (environ 300 ans avant J.-C.), plus précisément dans le Livre 7 (Propositions 1 et 2) et dans le Livre 10 (Propositions 2 et 3).

Des siècles plus tard, l'algorithme d'Euclide a été découvert indépendamment en Inde et en Chine, principalement pour résoudre des équations diophantiennes apparues en astronomie et pour réaliser des calendriers précis.

À la fin du 5ème siècle, le mathématicien et astronome indien Aryabhata a décrit l'algorithme comme le "pulvérisateur", peut-être en raison de son efficacité dans la résolution des équations diophantiennes.

Remerciements:

Joan Jareño (Creamat) (Ajout de lcm)