Se connecter
ou

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

I

PGCD de deux entiers et nombres premiers entre eux

\(\displaystyle{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 :

\(\displaystyle{PGCD\left(a;b\right)}\)

L'ensemble des entiers naturels diviseurs communs à 24 et 36 est \(\displaystyle{\left\{ 1;2;3;4;6;12 \right\}}\). Donc :

\(\displaystyle{PGCD\left(24;36\right)=12}\)

Soient deux entiers relatifs a et b, avec \(\displaystyle{a\neq0}\).

  • \(\displaystyle{PGCD\left(a;0\right)=a}\)
  • \(\displaystyle{PGCD\left(a;1\right)=1}\)
  • \(\displaystyle{PGCD\left(a;b\right)=PGCD\left(\left| a \right|;\left| b \right|\right)}\)
  • Si b divise a, alors \(\displaystyle{PGCD\left(a;b\right)=\left| b \right|}\)

−3 divise 15, donc :

\(\displaystyle{PGCD\left(15;-3\right)=\left| -3 \right|=3}\)

Algorithme d'Euclide

Soient deux entiers naturels non nuls a et b, avec \(\displaystyle{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 \(\displaystyle{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.

\(\displaystyle{72=48\times1+\color{Red}{24}}\)

\(\displaystyle{48=24\times2+0}\)

Donc :

\(\displaystyle{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 :

\(\displaystyle{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 \(\displaystyle{\left\{ 1;2;3;4;6;8;12;24 \right\}}\).

Soient des entiers naturels non nuls a, b et k.

\(\displaystyle{PGCD\left(ka;kb\right)=k\times PGCD \left(a;b\right)}\)

\(\displaystyle{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 \(\displaystyle{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 \(\displaystyle{\dfrac{a}{D}}\) et \(\displaystyle{\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 :

\(\displaystyle{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 :

\(\displaystyle{ua + vb = 1}\)

On a :

\(\displaystyle{5\times2+\left(-9\right)\times1=1}\)

5 et −9 sont donc premiers entre eux.

On a, pour tout entier relatif n :

\(\displaystyle{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 \(\displaystyle{15x=17y}\).

15 divise \(\displaystyle{17y}\). Or 15 et 17 sont premiers entre eux. Donc 15 divise y.