Le plus grand commun diviseur est une notion mathématique qui permet par exemple de simplifier les fractions. Pour cela on cherche tous les diviseurs communs entre 2 nombres, on rassemble les diviseurs identiques et on en prend le plus grand. Malheureusement cette approche naïve peut être très longue sur de grands nombres. On pourra cependant utiliser la décomposition en facteurs premiers ou alors l'algorithme d'Euclide pour arriver plus rapidement au résultat.

0:00 • Présentation
1:12 • Simplification de fraction avec le PGCD
4:42 • Approche naïve
8:37 • PGCD et décomposition en facteur premier
11:40 • Principe de l'algorithme d'Euclide
20:03 • Exemple avec l'algorithme d'Euclide
22:03 • Principe de l'algorithme d'Euclide optimisé
26:04 • Exemple avec l'algorithme d'Euclide optimisé
30:15 • Exemple complet par décomposition
37:23 • Exemple complet avec l'algorithme d'Euclide
40:05 • Exemple complet avec l'algorithme d'Euclide optimisé
43:08 • Conclusion