PGCD de deux entiers et nombres premiers entre eux
PGCD\left(a;b\right)
Soient a et b deux entiers relatifs dont l'un au moins est non nul. L'ensemble des diviseurs communs à a et b admet un plus grand élément, que l'on appelle le plus grand diviseur commun à a et b et que l'on note :
PGCD\left(a;b\right)
L'ensemble des entiers naturels diviseurs communs à 24 et 36 est \left\{ 1;2;3;4;6;12 \right\}. Donc :
PGCD\left(24;36\right)=12
Soient deux entiers relatifs a et b, avec a\neq0.
- PGCD\left(a;0\right)=|a|
- PGCD\left(a;1\right)=1
- PGCD\left(a;b\right)=PGCD\left(\left| a \right|;\left| b \right|\right)
- Si b divise a, alors PGCD\left(a;b\right)=\left| b \right|
-3 divise 15, donc :
PGCD\left(15;-3\right)=\left| -3 \right|=3
Algorithme d'Euclide
Soient deux entiers naturels non nuls a et b, avec b\lt a et r le reste de la division euclidienne de a par b. L'ensemble des diviseurs communs à a et b est confondu avec celui des diviseurs communs à b et r.
Lorsque b ne divise pas a, en appliquant cette propriété jusqu'à obtention d'un reste nul, on obtient PGCD\left(a;b\right) comme étant le dernier reste non nul. Ce procédé est appelé algorithme d'Euclide.
Recherchons le PGCD des nombres 72 et 48.
72=48\times1+\textcolor{Red}{24}
48=24\times2+0
Donc :
PGCD\left(72;48\right)=24
Soient deux entiers naturels non nuls a et b dont le PGCD est D. L'ensemble des diviseurs communs à a et b est l'ensemble des diviseurs de D.
On a :
PGCD\left(72;48\right)=24
Donc l'ensemble des entiers naturels diviseurs communs à 72 et 48 est l'ensemble des diviseurs de 24, soit \left\{ 1;2;3;4;6;8;12;24 \right\}.
Soient des entiers naturels non nuls a, b et k.
PGCD\left(ka;kb\right)=k\times PGCD \left(a;b\right)
PGCD\left(72;48\right)=PGCD\left(2\times36;2\times24\right)=2\times PGCD\left(36;24\right)
Nombres premiers entre eux
Deux nombres a et b sont premiers entre eux si et seulement si leur seul diviseur positif commun est 1, autrement dit si et seulement si PGCD\left(a;b\right)=1.
Soient a et b deux entiers naturels non nuls.
D est le PGCD de a et b si et seulement si \dfrac{a}{D} et \dfrac{b}{D} sont des entiers premiers entre eux.
Théorème de Bézout
Soient a et b deux entiers relatifs non nuls, et D leur PGCD. Alors il existe deux entiers relatifs u et v tels que :
ua+vb=D
Théorème de Bézout
D'après le théorème de Bézout, les entiers a et b sont premiers entre eux si et seulement s'il existe deux entiers relatifs u et v tels que :
ua + vb = 1
On a :
5\times2+\left(-9\right)\times1=1
5 et -9 sont donc premiers entre eux.
On a, pour tout entier relatif n :
n\times\left(-1\right)+\left(n+1\right)\times1=1
Donc deux entiers consécutifs sont toujours premiers entre eux.
Théorème de Gauss
Théorème de Gauss
Soient a, b et c trois entiers non nuls. Alors :
Si c divise ab et c premier avec a, alors c divise b .
Soit x et y deux entiers tels que 15x=17y.
15 divise 17y. Or 15 et 17 sont premiers entre eux. Donc 15 divise y.