Deux nombres entiers naturels sont dits premiers entre eux s'ils n'ont aucun diviseur commun autre que 1. Autrement dit, leur plus grand commun diviseur (PGCD) est 1.

Par exemple, considérons les nombres 8 et 15 :

• Les diviseurs de 8 sont : 1, 2, 4, 8.

• Les diviseurs de 15 sont : 1, 3, 5, 15.

Le seul diviseur commun à 8 et 15 est 1, donc 8 et 15 sont premiers entre eux.

Voyons un autre exemple avec les nombres 12 et 18 :

• Les diviseurs de 12 sont : 1, 2, 3, 4, 6, 12.

• Les diviseurs de 18 sont : 1, 2, 3, 6, 9, 18.

Les diviseurs communs de 12 et 18 sont : 1, 2, 3, 6. Leur plus grand diviseur commun est 6, donc 12 et 18 ne sont pas premiers entre eux.

En résumé, deux nombres sont premiers entre eux si le seul nombre qui les divise tous les deux est 1.

Le théorème de Bézout

Le théorème de Bézout énonce que pour deux nombres entiers $a$ et $b$ qui sont premiers entre eux, il existe toujours des entiers relatifs $u$ et $v$ tels que :

Cela signifie que l'on peut trouver des entiers $u$ et $v$ tels que la combinaison linéaire de $a$ et $b$ donne 1.

Exemple concret

Prenons les nombres 8 et 15, qui sont premiers entre eux. Selon le théorème de Bézout, il existe des entiers $u$ et $v$ tels que :

Nous pouvons trouver ces entiers en utilisant l'algorithme d'Euclide étendu. Après quelques calculs (non détaillés ici pour la simplicité), on trouve que :

Donc, $u = - 11$ et $v = 6$ sont des solutions de l'équation.