PGCD à partir des facteurs premiers

Énumérer les facteurs devient lent pour les nombres plus grands, et les décompositions en facteurs premiers sont plus rapides. Décompose les deux nombres en facteurs premiers : 45 est 3 × 3 × 5 et 75 est 3 × 5 × 5. Les nombres premiers qu’ils ont en commun sont un 3 et un 5.

Multiplie les facteurs premiers communs : 3 × 5 donne 15, le PGCD de 45 et 75. Un nombre premier ne compte comme facteur commun que le nombre de fois où il apparaît dans les deux nombres : 45 a deux 3, mais 75 n’en a qu’un, donc on n’inclut qu’un seul 3.

Pourquoi cela fonctionne : un facteur commun ne peut être constitué que de nombres premiers présents dans les deux nombres. En prenant chaque nombre premier commun autant de fois que les deux nombres le permettent, on obtient le plus grand facteur commun. Avec les exposants, prenez chaque nombre premier commun avec son plus petit exposant : 3^2 × 5 et 3 × 5^2 donnent 3 × 5.