Qu'est-ce que le PGCD ?
Le PGCD (Plus Grand Commun Diviseur) de deux nombres entiers est le plus grand nombre qui divise ces deux nombres sans reste. Par exemple, le PGCD de 12 et 18 est 6, car 6 est le plus grand nombre qui divise à la fois 12 (12 ÷ 6 = 2) et 18 (18 ÷ 6 = 3). Le PGCD est fondamental en arithmétique : il sert notamment à simplifier les fractions en divisant le numérateur et le dénominateur par leur PGCD.
L'algorithme d'Euclide
L'algorithme d'Euclide est la méthode la plus efficace pour calculer le PGCD. Il repose sur un principe simple : le PGCD de deux nombres ne change pas si on remplace le plus grand par le reste de la division du plus grand par le plus petit. On répète l'opération jusqu'à obtenir un reste nul. Exemple : PGCD(48, 18) → 48 = 2×18 + 12, puis PGCD(18, 12) → 18 = 1×12 + 6, puis PGCD(12, 6) → 12 = 2×6 + 0. Le PGCD est 6.
Applications pratiques du PGCD
Le PGCD est utilisé pour simplifier des fractions (ex. 12/18 = 2/3 en divisant par le PGCD 6), pour découper un terrain en parcelles carrées de taille maximale, ou pour résoudre des problèmes de répartition équitable. En informatique, il intervient dans les algorithmes de cryptographie (RSA) et dans le calcul de rapport d'aspect des écrans (ex. 1920×1080 → PGCD = 120 → rapport 16:9).