Cours sur le PGCD et PPCM

PGCD - PPCM 1 Plus grand diviseur commun de deux entiers 1.1 DØ?nition - Exemples DØ?nition 1 Soient a et b deux ØlØment deZ. aZ+bZ est un sous-groupe deZ donc il existe 2N tel que aZ+bZ = Z. On appelle le plus grand diviseur commun de a et b et on note = pgcd(a;b) ou = a^b. Exemple 2 On a vu dans le chapitre prØcØdent pgcd(2;3) = 1 et pgcd(10;25) = 5. Remarque 3 Pour tout a et b dansZ, pgcd(a;b) = pgcd(b;a) = pgcd(jaj;jbj). Soient a;b2N alors ajb() pgcd(a;b) = a DØmonstration. Le premier point dØcoule du fait quejaj = aZ. Montrons le second on a ajb() bZ aZ() aZ+bZ = aZ() pgcd (a;b) = a Proposition 4 Soient a et b deux entiers relatifs. Soit 2N. Alors = pgcd(a;b) si et seulement si l?entier divise a et b si d est un diviseur de a et de b alors d divise Cela explique le nom de plus grand diviseur commun pour . DØmonstration. Notons = pgcd(a;b). On a aZ Z donc ja, de mŒme bZ Z donc jb. Donc est un diviseur commun ? a et b. Soit d un diviseur de a et b, alors aZ dZ et bZ dZ donc aZ[bZ dZ donc (par dØ?nition de la somme de deux sous-groupes) aZ+bZ dZ donc Z dZ et donc dj . RØciproquement soit un entier positif vØri?ant : l?entier divise a et b si d est un diviseur de a et de b alors d divise Il faut montrer que = pgcd(a;b). On a aZ Z et bZ Z donc aZ+bZ Z et aZ+bZ = pgcd(a;b)Z donc jpgcd(a;b). D?autre part pgcd(a;b) est un diviseur de a et de b donc par dØ?nition de on a pgcd(a;b)j .