Le PGCD, les théorèmes de Bézout et de Gauss Cours

Sommaire

IPGCD de deux entiers et nombres premiers entre euxIIThéorème de BézoutIIIThéorème de Gauss
I

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+\color{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.

II

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.

III

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.