Nombres premiers entre eux

vignette|Le segment ne passe par aucun point du réseau (hormis les points à ses extrémités), ce qui montre que 4 et 9 sont 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 à 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é la notation . 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'. 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. Dans ce qui suit, a et b désignent deux entiers relatifs. Si a est premier avec divers autres entiers alors il est premier avec leur produit, puisque tout diviseur non trivial de ce produit doit diviser l'un des entiers, et donc ne pas diviser a. Si a est premier avec b, a + bc est premier avec b quel que soit l'entier c. En effet, pgcd(b, a + bc) = pgcd(b, a). Si a est premier avec b, alors a + b est premier avec a et b : ce n'est guère que le résultat ci-dessus appliqué à c = 1, et appliqué à nouveau en inversant les rôles de a et b. Un nombre p est premier si, et seulement si, il est premier avec tout nombre qu'il ne divise pas.