Nombres premiers entre eux

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 pour les entiers naturels dans le livre VII des Éléments d'Euclide, puis étendue aux entiers relatifs.

Des notations standard pour deux entiers Modèle:Mvar et Modèle:Mvar premiers entre eux sont : Modèle:Math ou Modèle:Math. Ronald Graham, Donald Knuth et Oren Patashnik ont aussi proposé la notation $a\perp b$Modèle:Sfn.

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'Modèle:Lien.

Le nombre d'entiers premiers avec un entier positif Modèle:Math et compris entre 1 et Modèle:Math est égal à Modèle:Math, où Modèle:Math est la fonction phi d'Euler.

Propriétés

Propriétés élémentaires

Dans ce qui suit, a et b désignent deux entiers relatifsModèle:Sfn.

1. Si a est premier avec divers autres entiers alors il est premier avec leur produit, puisque tout diviseur premier de ce produit doit diviser l'un des entiers, et donc ne pas diviser a.
2. 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).
3. Si a est premier avec b, alors a + b est premier avec a et b : c'est le résultat ci-dessus appliqué à c = 1, et appliqué à nouveau en inversant les rôles de a et b.
4. Un nombre p est premier si, et seulement si, il est premier avec tout nombre qu'il ne divise pas. En effet, si p est premier et a un facteur commun non trivial avec un nombre a, ce facteur ne peut être que p, et réciproquement, si p n'est pas premier, il est divisible par un facteur d non trivial et différent de p, donc p n'est pas premier avec d.
5. Si a est premier avec b, alors aModèle:Exp est premier avec bModèle:Exp, quels que soient les entiers naturels m et n : cela provient du fait que tout facteur premier d'une puissance entière kModèle:Exp divise aussi k, en vertu de la décomposition de k en produit de facteurs premiers.
6. Si m et n sont des entiers strictement positifs, alors la réciproque a lieu : a est premier avec b lorsque aModèle:Exp est premier avec bModèle:Exp, ce qu'on déduit du fait que tout facteur premier d'un entier k divise aussi kModèle:Exp, si s > 0.
7. Si a est premier avec b, alors aModèle:Exp + bModèle:Exp est premier avec a et b quels que soient les entiers naturels m et n : ceci découle des propriétés 1 et 5 ci-dessus.
8. Toute fraction rationnelle q peut s'écrire sous forme dite « réduite » : q = a/b, où a est premier avec b.
9. Si $\frac{a}{b}$ et $\frac{c}{d}$ sont des fractions rationnelles réduites dont les dénominateurs sont premiers entre eux, alors la représentation de leur somme sous la forme $\frac{ad+bc}{bd}$ est d'ores et déjà réduite. En effet, bc est premier avec d et ad avec b en vertu des définitions et des hypothèses. Donc Modèle:Nobr est premier avec b et d par la deuxième propriété listée ci-dessus.

Théorème de Bachet-Bézout

Modèle:Article détaillé Les entiers relatifs a et b sont premiers entre eux si et seulement s’il existe des entiers relatifs x et y tels que ax + by = 1.

Cette condition équivaut à : b a un inverse pour la multiplication modulo a, c'est-à-dire : il existe un nombre entier y tel que by ≡ 1 (mod a).

Lemme de Gauss

Modèle:Article détaillé Si a et b sont premiers entre eux et a divise un produit bc, alors a divise c.

• Ainsi, si a et b sont premiers entre eux et bx ≡ by (mod a), alors x ≡ y (mod a) puisque a divise b(x-y). En d'autres termes : b est simplifiable dans l'anneau ℤ/aℤ des entiers modulo a.
• En considérant l'équation en nombres de la demi-droite ay = bx avec x > 0, on en déduit encore que y doit être multiple de b et x multiple de a. Autrement dit, deux entiers a et b sont premiers entre eux si et seulement si le point de coordonnées (a, b) dans un repère cartésien est « visible » de l'origine (0, 0), dans le sens où il n'y a pas de point de coordonnées entières entre l'origine et (a, b).
• Si $ab=a^{\prime }{b}^{\prime }$ où $a$ est premier avec $b^{\prime }$ et $b$ est premier avec $a^{\prime }$, alors $a=\pm a^{\prime }$ et $b=\pm b^{\prime }$, les signes étant identiques. En effet, $a$ divise $a^{\prime }$ et $b$ divise $b^{\prime }$ par le lemme de Gauss, et pour la même raison, $a^{\prime }$ divise $a$ et $b^{\prime }$ divise $b$; donc $a^{\prime }=\pm a$ et $b^{\prime }=\pm b$, et l'équation d'hypothèse implique que les signes sont identiques.
• Si a et b sont positifs et premiers entre eux, et si ab est une puissance de n, alors a et b sont aussi des puissances de n. Notons en effet Modèle:Nobr. Alors c est égal à 1, auquel cas tout est trivial, ou est produit d'un nombre fini de puissances pModèle:Exp de facteurs premiers distincts p. Ainsi cModèle:Exp est le produit des pModèle:Exp. Mais pModèle:Exp ne saurait avoir de facteurs communs non triviaux avec a et b à la fois, sans quoi p diviserait ce facteur et serait un facteur commun à a et à b. Donc pModèle:Exp divise l'un ou l'autre des nombres a et b par le lemme de Gauss. Comme c'est vrai pour chacun des pModèle:Exp, a est produit d'une partie des pModèle:Exp, tandis que b est produit de l'autre partie, ce qui permet de conclure.

Théorème des restes chinois

Modèle:Article détaillé Deux entiers a et b sont premiers entre eux, si et seulement si tout système de congruences de la forme Modèle:Math et Modèle:Math a une infinité de solutions en nombres, d'ailleurs décrites par une congruence unique de la forme Modèle:Math.

Cette équivalence se généralise au cas d'un ensemble de nombres premiers deux à deux.

Indicatrice d'Euler

L'indicatrice d'Euler, qu'on note habituellement $\phi (n)$, est la fonction qui, à tout entier Modèle:Math, associe le nombre d'entiers premiers à Modèle:Mvar dans l'intervalle $]0,n]$.

Une expression explicite de l'indicatrice d'Euler s'obtient à partir de la décomposition en facteurs premiers de n :

$\mathrm{s}\mathrm{i}n=\prod _{i=1}^r{p}_i^{k_i}\mathrm{a}\mathrm{l}\mathrm{o}\mathrm{r}\mathrm{s}\phi (n)=\prod _{i=1}^r(p_i-1)p_i^{k_i-1}=n\prod _{i=1}^r(1-\frac{1}{p_i}).$

Pour tout entier Modèle:Math, [[Indicatrice_d'Euler#Arithmétique_modulaire|Modèle:Math est pair et la somme de tous les entiers positifs inférieurs et premiers à Modèle:Mvar est égale à Modèle:MvarModèle:Sfrac]].

Extension à un ensemble quelconque d'entiers

Modèle:Ancre Les nombres d'un ensemble quelconque D (fini ou infini) d'entiers sont dits premiers entre eux dans leur ensemble si 1 est leur plus grand commun diviseur.

Ils sont premiers entre eux deux à deux si pour tous a et b distincts dans D, a et b sont premiers entre eux.

La présence dans D de deux nombres premiers entre eux est une condition suffisante, mais non nécessaire, pour que les entiers de D soient premiers entre eux dans leur ensemble. Par exemple, 6, 14 et 21 sont premiers entre eux dans leur ensemble, mais aucun couple extrait de ce triplet n'est formé de deux nombres premiers entre eux.

Pour que des nombres $a_1,a_2,\dots a_n$ soient premiers dans leur ensemble, il faut et il suffit qu'ils satisfassent à une relation de Bezout de la forme

$a_1{x}_1+a_2{x}_2+\cdots +a_n{x}_n=1$

pour des entiers relatifs $x_1,\dots x_n.$

Des nombres $a_1,a_2,\dots a_n$ premiers deux à deux vérifient par exemple cette propriété: en notant ${\hat{a}}_i$ le produit de tous les $a_j$ pour lesquels $j=i$, chacun des $a_i$ (et donc le produit de tous les $a_i$) sont premiers avec le nombre

${\hat{a}}_1+{\hat{a}}_2+\cdots +{\hat{a}}_n.$

En effet, pour tout i donné, chaque ${\hat{a}}_j$ tel que $j=i$ est multiple de $a_i$, tandis que ${\hat{a}}_i$ est premier avec $a_i$. Donc la somme S des ${\hat{a}}_j$ est multiple de $a_i$, et $S+{\hat{a}}_i$, ou bien ${\hat{a}}_1+{\hat{a}}_2+\cdots +{\hat{a}}_n$, est premier avec $a_i$.

Généralisation dans les anneaux

Des idéaux I et J d'un anneau commutatif A sont dits premiers entre eux si I + J = A (par exemple : deux idéaux maximaux distincts sont premiers entre eux). Cela généralise l'identité de Bézout : si I et J sont premiers entre eux, alors IJ = I∩J et le théorème des restes chinois généralisé s'applique ; de plus, si K est un troisième idéal tel que I contient JK, alors I contient K.

Avec cette définition, dans l'anneau ℤ des entiers relatifs, les idéaux principaux (a) et (b) sont premiers entre eux si et seulement si les entiers a et b sont premiers entre eux.

Voir aussi l'article Primalité dans un anneau, pour la définition générale d'éléments premiers entre eux dans un anneau (qui coïncide pour Z avec la condition précédente).

Probabilités

Modèle:Article détaillé Quand n tend vers l'infini, la probabilité pour que deux nombres entiers inférieurs à n soient premiers entre eux tend vers [[Produit eulérien#Calcul pour s égal à 2|6/Modèle:MathModèle:2]]. Plus généralement, la probabilité que k entiers inférieurs à n choisis au hasard soient premiers entre eux tend vers 1/ζ(k).

Articles connexes

• Nombres premiers