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.
Corollaire : Thé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.
Explication : Condition 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émonstration : Ré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).\)