Nombres premiers entre eux

En mathématiques, on dit que deux entiers a et b sont premiers entre eux, que a est premier avec b ou premier à^[1] b ou encore que a et b sont copremiers (ou encore étrangers) si leur plus grand commun diviseur est égal à 1 ; en d'autres termes, s'ils n'ont aucun diviseur autre que 1 et –1 en commun. De manière équivalente, ils sont premiers entre eux s'ils n'ont aucun facteur premier en commun.

Par exemple, 6 et 35 sont premiers entre eux, mais 6 et 27 ne le sont pas parce qu'ils sont tous les deux divisibles par 3. Le nombre 1 est premier avec tout entier, tandis que 0 est uniquement premier avec 1 et –1.

Cette notion a été introduite dans le livre VII des Éléments d'Euclide.

Des notations standard pour deux entiers a et b premiers entre eux sont : pgcd(a, b) = 1 ou a∧b = 1. Ronald Graham, Donald Knuth et Oren Patashnik ont aussi proposé^[2] la notation ${\displaystyle a\perp b}$.

Un moyen rapide pour déterminer si deux nombres entiers sont premiers entre eux est l'algorithme d'Euclide, ou ses versions plus rapides telles que l'algorithme du PGCD binaire ou l'algorithme du PGCD de Lehmer (en).

Le nombre d'entiers premiers avec un entier positif n et compris entre 1 et n est égal à φ(n), où φ est la fonction phi d'Euler.