Si et sont premiers entre eux alors et sont premiers entre eux.

Supposons et premiers entre eux. Soit un diviseur positif commun à et alors divise et . Ainsi, divise et , avec et premiers entre eux, donc . D'où .