Entiers premiers entre eux

Plan du chapitre "Arithmétique dans ℤ"

Couples d’entiers premiers entre eux

Définition
Soit {a} et {b} deux entiers relatifs.
On dit que {a} et {b} sont premiers entre eux (ou encore étrangers) si {a\wedge b=1}.

Il revient au même d’écrire {\mathcal{D}(a)\cap\mathcal{D}(b)=\{-1,1\}}.
Cela équivaut aussi à dire que le seul diviseur commun strictement positif de {a} et {b} est {1}.
Dans le cas où {a=b=0}, on rappelle que {a\wedge b=0}, donc le problème ne pose pas.
Seuls les entiers {1} et {-1} sont premiers avec eux-mêmes.

Comme on a toujours {a\wedge b=\left|a\right|\wedge\left|b\right|}, on peut se ramener au cas de deux entiers naturels dont l’un au moins est non nul. Et dire alors que {a} et {b} sont premiers entre eux, c’est dire que le dernier reste non nul dans leur algorithme d’Euclide est égal à {1}.

On ne confondra pas cette notion avec celle de “nombre premier” (voir plus loin).

Proposition (les quotients de deux entiers par leur pgcd sont premiers entre eux)
Soit {a} et {b} deux entiers relatifs (non tous deux nuls), et {d} leur pgcd (donc {d>0}).
Les deux entiers {a'} et {b'} tels que {a=da'} et {b=db'} sont premiers entre eux.

Réciproquement, si {u\wedge v=1}, et pour tout {\delta} dans {\mathbb{N}^{*}}, le pgcd de {\delta u} et {\delta v} est égal à {\delta}.

Avec les notations précédentes, le rationnel {r=\dfrac{a}{b}} admet la forme dite irréductible : {r=\dfrac{a'}{b'}}.
Cette forme irréductible (simplifiée) est unique si on impose un dénominateur strictement positif.

Le théorème de Bézout et ses conséquences

Proposition (théorème de Bézout)
Soit {a} et {b} deux entiers relatifs. Les deux propositions suivantes sont équivalentes :

  • les entiers {a} et {b} sont premiers entre eux.
  • il existe deux entiers relatifs {u} et {v} tels que {au+bv=1}.

Le théorème de Bézout a des conséquences fondamentales en arithmétique des entiers :

Proposition (lemme de Gauss)
Soit {a,b,c} trois entiers relatifs.
Si {a} divise {bc} et si {a} est premier avec {b}, alors {a} divise {c}.
Proposition (résolution de ax+by=1 quand a et b sont premiers entre eux)
Soit {a} et {b} deux entiers relatifs premiers entre eux.
Alors il existe une infinité de couples {(x,y)} de {\mathbb{Z}^2} tels que {ax+by=1}.
Si {(x_0,y_0)} est l’un d’eux, les autres sont donnés par {\begin{cases}x=x_0+kb\cr y=y_0-ka\end{cases}} avec {k} dans {\mathbb{Z}}.
Proposition (entier premier avec un produit)
Soit {a,b,c} trois entiers relatifs. Les deux propositions suivantes sont équivalentes :

  • l’entier {a} est premier avec l’entier {b} et avec l’entier {c}.
  • l’entier {a} est premier avec le produit {bc}.

Plus généralement, soient {a_{1},a_{2},\ldots,a_{m}} et {b_{1},b_{2},\ldots,b_{n}} deux familles d’entiers relatifs.

Les deux propositions suivantes sont équivalentes :

  • chacun des entiers {a_{1}}, {a_{2}}, {\ldots} , {a_{m}} est premier avec chacun des entiers {b_{1}}, {b_{2}}, {\ldots} , {b_{n}}.
  • le produit {a_{1}a_{2}\cdots a_{m}} est premier avec le produit {b_{1}b_{2}\cdots b_{n}}.

Par exemple, si {a\wedge b=1}, alors {a^m\wedge b^n=1}.

Proposition (divisibilité par deux entiers premiers entre eux)
Soit {a,b,c} trois entiers relatifs, les entiers {a} et {b} étant supposés premiers entre eux.
Si l’entier {c} est divisible par {a} et par {b}, alors il est divisible par leur produit {ab}.

Plus généralement si les entiers {a_1}, {a_2}, {\ldots}, {a_n} sont premiers entre eux deux à deux, et si l’entier {c} est divisible par chacun des {a_k}, alors il est divisible par leur produit.

Pgcd de plusieurs entiers

Proposition (associativité du pgcd et du ppcm)
Pour tous entiers relatifs {a,b,c}, on a les égalités {\begin{cases}a\wedge(b\wedge c)=(a\wedge b)\wedge c\cr a\vee(b\vee c)=(a\vee b)\vee c\end{cases}}

L’associativité (et la commutativité) du pgcd et du ppcm ont pour conséquence que si on se donne {n} entiers relatifs {a_1}, {a_2}, {\ldots}, {a_n}, alors les notations {a_1\wedge a_2\wedge\cdots\wedge a_n} et {a_1\vee a_2\vee\cdots\vee a_n} ont un sens, indépendamment de l’ordre des facteurs {a_k} et de celui dans lequel on effectue les calculs.

On peut alors poser la définition suivante :

Définition
Soit {a_1}, {a_2}, {\ldots}, {a_n}, une famille de {n} entiers relatifs, avec {n\ge2}.
L’entier {a_1\wedge a_2\wedge\cdots\wedge a_n} est appelé le pgcd des entiers {a_1}, {a_2}, {\ldots}, {a_n}.
L’entier {a_1\vee a_2\vee\cdots\vee a_n} est appelé le ppcm des entiers {a_1,a_2,\ldots,a_n}.

Caractérisation du pgcd et du ppcm

  • L’entier {d=a_1\wedge a_2\wedge\cdots\wedge a_n} est l’unique entier naturel tel que :{\mathcal{D}(a_1)\cap\mathcal{D}(a_2)\cap\cdots\cap\mathcal{D}(a_n)=\mathcal{D}(d)}
    Autrement dit, les diviseurs communs aux entiers {a_1}, {a_2}, {\ldots}, {a_n} sont les diviseurs de leur pcgd.
  • L’entier {m=a_1\vee a_2\vee\cdots\vee a_n} est l’unique entier naturel tel que : {a_1\mathbb{Z}\cap a_2\mathbb{Z}\cap \cdots\cap a_n\mathbb{Z}=m\mathbb{Z}}
    Les multiples communs à {a_1,a_2,\ldots,a_n} sont donc les multiples de leur ppcm.
Proposition (factorisations et simplifications dans un calcul de pgcd/ppcm)
Soit {a_1,\ldots,a_n} des entiers relatifs. Soit {k} un entier strictement positif.

On les égalités : {\begin{cases}(k a_1)\wedge(k a_2)\wedge\cdots\wedge(k a_n)=k(a_1\wedge a_2\wedge\cdots\wedge a_n)\cr (k a_1)\vee(k a_2)\vee\cdots\vee(k a_n)=k(a_1\vee a_2\vee\cdots\vee a_n)\end{cases}}

Soit {k} un diviseur commun des {a_{k}}. Alors {\dfrac{a_1}{k}\wedge\dfrac{a_2}{k}\wedge\cdots\wedge\dfrac{a_n}{k}=\dfrac{a_1\wedge a_2\wedge\cdots\wedge a_n}{k}}.

De la même manière {\dfrac{a_1}{k}\vee\dfrac{a_2}{k}\vee\cdots\vee\dfrac{a_n}{k}=\dfrac{a_1\vee a_2\vee\cdots\vee a_n}{k}}.

Proposition (relation de Bézout)
Soit {a_1,a_2,\ldots,a_n} une famille de {n} entiers relatifs, avec {n\ge2}. Soit {d} leur pcgd.
Alors il existe des entiers relatifs {u_1,u_2,\ldots,u_n} tels que : {a_1u_1+a_2u_2+\cdots+a_nu_n=d}.

Entiers premiers entre eux dans leur ensemble

Définition (entiers premiers entre eux dans leur ensemble)
Soit {a_1,a_2,\ldots,a_n} une famille de {n} entiers relatifs, avec {n\ge2}.
On dit que ces {n} entiers sont premiers entre eux dans leur ensemble si leur pgcd est égal à {1}.
Cela équivaut à dire que le seul diviseur positif commun à {a_1,a_2,\ldots,a_n} est {1}.
Proposition (caractérisation par une identité de Bézout)
Soit {a_1,a_2,\ldots,a_n} une famille de {n} entiers relatifs, avec {n\ge2}.
Les deux proposition suivantes sont équivalentes :

  • les entiers {a_1,a_2,\ldots,a_n} sont premiers entre eux dans leur ensemble.
  • il existe {n} entiers relatifs {u_1,u_2,\ldots,u_n} tels que : {a_1u_1+a_2u_2+\cdots a_{n}u_{n}=1}.

Remarques

  • Ne pas confondre “premiers entre eux deux à deux” et “premiers entre eux dans leur ensemble”.

    Plus précisément : si deux au moins des entiers {a_1,\ldots,a_n} sont premiers entre eux, et a fortiori si les entiers {a_1,\ldots,a_n} sont premiers entre eux deux à deux, alors ils le sont dans leur ensemble.

    Dès que {n\ge3}, la réciproque est fausse comme le montre l’exemple de {6,10,15}.
    On a en effet {\begin{cases}6\wedge 10\wedge 15=1\text{\ car\ }6+10-15=1\\6\wedge10=2,\ 6\wedge15=3,\ 10\wedge15=5\end{cases}}

  • Soit {d} un diviseur strictement positif commun aux entiers {a_1,\ldots,a_n}.
    Alors {d=a_1\wedge a_{2}\wedge\ldots\wedge a_n\iff} les entiers {\dfrac{a_k}{d}} sont premiers entre eux dans leur ensemble.
  • Si {a_1,\ldots,a_n} sont premiers entre eux deux à deux, alors {a_1\vee a_2\vee\cdots\vee a_n=a_1a_{2}\cdots a_n}.
  • Attention : l’égalité {(a\wedge b)(a\vee b)=ab} ne se généralise pas à plus de deux entiers.

    Par exemple, avec {a=6}, {b=10}, {c=15}, on a : {a\wedge b\wedge c=1,\ a\vee b\vee c=30,\ abc=900}

Un peu de programmation \texttt{Python}

On utilise ici les fonctions pgcd et ppcm définies précédemment.

Pour calculer le pgcd ou le ppcm des entiers d’une liste, on importe la fonction reduce du module functools, qui offre un moyen d’itérer une même fonction de deux arguments.

def mpgcd(seq):
from functools import reduce
return reduce(pgcd,seq)
def mppcm(seq):
from functools import reduce
return reduce(ppcm,seq)

Voici deux exemples très simples d’utilisation de ces deux fonctions :

>>> mpgcd([378, 630, 882, 945])
63
>>> mppcm([6, 10, 14, 15, 21])
210

Page précédente : pgcd et algorithme d’Euclide
Page suivante : nombres premiers