12.1 Notion de pgcd (plus grand commun diviseur)

Etant donné deux nombres entiers, leur pgcd désigne leur plus grand commun diviseur.

• Par exemple, 42 et 28 ont pour pgcd 14 (c’est le plus grand nombre possible qui divise à la fois 28 et 42)
• 25 et 55 ont pour pgcd 5.
• 42 et 23 ont pour pgcd 1.

Lorsque deux nombres ont pour pgcd 1, on dit qu’ils sont premiers entre eux. Ainsi sur l’exemple précédent, 42 et 23 sont premiers entre eux. Cela signifie qu’ils n’ont aucun diviseur commun hormis 1 (bien sûr, il divise tout entier!).