Nombres premiers entre eux

Définition

On dit que deux nombres \(a\) et \(b\) sont premiers entre eux si leur pgcd pgcd\((a,b)\) est égal à 1.

CorollaireThéorème de Bézout

Soient \(a\) et \(b\) deux entiers non nuls. On a l'équivalence :

pgcd\((a,b) = 1 \Leftrightarrow(\exists u,v \in \mathbb Z, au + bv = 1).\)

Si \(a\) et \(b\) sont premiers entre eux alors il existe \(u\) et \(v\) tels que \(ua + vb = 1\) et réciproquement si un tel couple existe, on sait que pgcd\((a,b)\) égale 1, puisque tous les entiers \(ax + by\) sont des multiples du pgcd de \(a\) et \(b.\) Dans ce cas, le pgcd de \(a\) et \(b\) divise 1. Il est donc égal à 1.

Décomposition de deux nombres à l'aide de leur pgcd

Soient deux entiers \(a\) et \(b\) avec leur pgcd \(d.\) Notons \(a'\) et \(b'\) les quotients de \(a\) et \(b\) par \(d.\) Donnons nous deux entiers \(u\) et \(v\) satisfaisant à la relation de Bézout : \(au + bv = d.\)

\(\begin{array}{ccc}a&=&da'\\b&=&db'\\au + bv&=&d\\da' u + db'v&=&d\\a'u + b'v&=&1\end{array}\)

donc d'après le corollaire du théorème de Bézout \(a'\) et \(b'\) sont premiers entre deux.

ExplicationCondition nécessaire et suffisante pour qu'un nombre soit le pgcd de a et b :

Si \(a\) et \(b\) sont deux entiers et \(d\) un diviseur positif commun de \(a\) et de \(b,\) si \(a = da'\) et \(b = db',\) on a l'équivalence :

\(d = \textrm {pgcd} (a,b) \Leftrightarrow \textrm {pgcd} (a',b') = 1\)

DémonstrationRéciproque

Si \(\delta\) est un diviseur commun positif à \(a\) et \(b,\) si \(a = \delta a_1\) et \(b = \delta b_1,\) et si pgcd\((a_1, b_1) = 1\) alors \(\delta = \textrm {pgcd} (a,b).\)

\(\delta\) est un diviseur commun à \(a\) et \(b,\) donc \(\delta\) est un diviseur du pgcd \(d\) de \(a\) et \(b :\) il existe un entier \(\delta'\) tel que \(\delta \delta' = d\)

\(a = da' = \delta \delta' a' = \delta (\delta' a') \quad \textrm {et} \quad b = db' = \delta \delta' b' = \delta (\delta'b')\)

Donc d'après les hypothèses, \(\delta'a' = a_1\) et \(\delta'b' = b_1. \delta'\) est un diviseur commun à \(a_1\) et \(b_1,\) supposés premiers entre eux. pgcd\((a_1,b_1) = 1\) donc \(\delta'\) divise 1 et est positif.

Donc \(\delta' = 1.\) On a donc montré \(\delta = \textrm {pgcd} (a,b).\)