Plus grand commun diviseur de deux entiers relatifs non tous deux nuls (PGCD)
 

Diviseur commun de deux entiers relatifs non tous deux nuls

Soit a et b deux entiers relatifs non nuls, tout entier qui divise à la fois a et b est appelé diviseur commun de a et b.

Définition du PGCD de deux entiers relatifs non tous deux nuls

Soit a et b deux entiers relatifs non tous deux nuls, l'ensemble des diviseurs communs à a et b admet un plus grand élément appelé le PGCD de a et b. On le note .

Propriétés du PGCD

L'ensemble des diviseurs communs de a et b est l'ensemble des diviseurs du PGCD de a et b. Si a et b sont deux entiers naturels non nuls et si a divise b, alors . Si a est un entier relatif non nul et , alors . Soit a et b deux entiers relatifs non tous deux nuls. Si , alors .

Méthodes pour déterminer le PGCD de deux entiers naturels        non nuls

A l'aide de la décomposition en nombres premiers Soit a et b deux entiers naturels non nuls.   et .   sont des nombres premiers distincts.   et sont des entiers naturels éventuellement nuls.   pour tout indice i vérifiant : . Exemple : déterminer .   et donc .   A l'aide de l'algorithme d'Euclide Soit a et b sont deux entiers naturels non nuls. La suite des divisions euclidiennes : de a par ,                               avec , de b par (si ),              avec , de par (si ),            avec , de par (si ), avec , permet de définir une suite strictement décroissante d'entiers positifs. Le dernier reste non nul est alors le PGCD de a et b (si , alors c'est b). Exemple : déterminer le Donc .

Nombres premiers entre eux

Définition : soit a et b deux entiers relatifs non nuls ensemble. Si , alors on dit que a et b sont premiers entre eux. On dit aussi que a et b sont étrangers. Propriété : soit a et b deux entiers relatifs non tous deux nuls.  Si , alors il existe deux entiers relatifs a' et b' premiers entre eux tels que : .

Théorème de Bezout

Théorème : soit a et b deux entiers relatifs non nuls et d leur PGCD. Il existe deux entiers relatifs u et v tels que : . Caractérisation des nombres premiers entre eux : égalité de Bezout Deux entiers relatifs non nuls sont premiers entre eux si et seulement si il existe deux entiers relatifs u et v tels que : .

Méthode pour déterminer les coefficients dans l'égalité        de Bezout

Soit a et b deux entiers naturels non nuls ; d est leur PGCD. D'après le théorème de Bezout il existe deux entiers relatifs u et v tels que : . Le but est de donner un algorithme permettant de déterminer u et v. On met en œuvre l'algorithme d'Euclide et on calcule les restes successifs en fonction de a et b.Le dernier reste non nul est le PGCD. On développe alors les calculs de façon à faire apparaître à chaque étape une écriture du reste de la forme . Exemple : déterminons des entiers relatifs u et v tels que : .   et .   soit donc ,   soit donc ,   soit donc ,   soit donc ,  . Par conséquent, on a :  ; et .

Théorème de Gauss

Théorème Soit a, b et c des entiers relatifs non nuls. Si , alors . Conséquences Soit a, b et c des entiers relatifs non nuls. Si , alors .

Méthode pour résoudre dans Z2 : ax + by = d        où d = PGCD(a ; b)

Une équation diophantienne est une équation à coefficients entiers, et dont les inconnues sont entières. On résout ces équations dans l'ensemble des couples d'entiers relatifs . On pose :  ; , avec a' et b' premiers entre eux.   avec a' et b' premiers entre eux. 1ere étape : recherche d'une solution particulière D'après le théorème de Bezout, il existe deux entiers relatifs et tels que : . 2ème étape : recherche des solutions générales   Or D'après le théorème de Gauss, a' divise , ce qui équivaut à : « il existe un entier relatif k tel que  ». Les solutions sont les couples de la forme avec k dans Z.