Soit d un diviseur commun de a et b alors d divise toute combinaison linéaire de a et b. Donc d divise et .

Et par conséquent d est un diviseur commun de N et P.

Non, la réciproque est fausse. Pour s'en convaincre, il suffit de poser et .

Dans ce cas on a et . 2 est un diviseur commun de N et P, par contre ce n'est pas un diviseur commun de a et b.