Chapitre 2 : PGCD & PPCM TS Spé

1. PGCD & PPCM

Définitions : Soit a et b deux entiers relatifs non nuls.

L'ensemble des diviseurs communs à a et b admet un plus grand élément D , appelé le PGCD de a et de b .L'ensemble des multiples communs strictement positifs de a et de b admet un plus petit élément M , appelé PPCM de a et de b .

Notations: D=PGCD a ;b et M=PPCM a ;b .

Détermination pratique :A la main, lorsque les nombres ne sont pas trop grands. ex : PGCD 420 ;1386 ?A la calculatrice, les instructions existent seulement pour des modèles "sophistiqués". Pour les autres, il faut écrire un programme qui repose sur l'algorithme d'Euclide (voir plus loin)Avec un ordinateur, utiliser un tableur et encore l'algorithme d'Euclide.

2. Nombres premiers entre eux

Définition : On dit que deux entiers relatifs sont premiers entre eux lorsque leur PGCD est égal à 1.

Résultats connus Soit a et b deux entiers non nuls.

La fraction ab est irréductible lorsque a et b sont premiers entre eux.

Le plus petit dénominateur commun de deux fractions est le PPCM des deux dénominateurs.

3. Algorithme d'Euclide

Il permet de calculer le PGCD d deux nombres a et b entiers naturels non nuls. Il est important de rappeler qu'un algorithme est une suite d’instructions (parfois répétitives : boucles) , qui une fois exécutée correctement, conduit à un résultat.

Théorème : soit a et b deux entiers naturels non nuls. La suite des divisions euclidiennes : de a par b de b par r 0 (si r 0≠0 ) de r 0 par r 1 (si r 1≠0 )

.......................... de r n– 1 par r n (si r n≠0 )

a=bq0r0 ;b=r 0q1r1 ;r 0=r 1q2r 2 ;.................................r n– 1=r nqn1r n1

finit par s'arrêter, un des restes r i étant non nul.Le dernier reste non nul est alors le PGCD de a et de b (si r 0=0 , c'est b )

2010@My Maths Space 1/3

Chapitre 2 : PGCD & PPCM TS Spé

Exemple : Déterminer le PGCD de 1958 et de 4539.

Avec un logiciel de codage d'algorithme (ALGOBOX)

Déclaration de variables.

Boucle "Tant que". Corps de l'algorithme.

Avec la calculatrice

4. Théorèmes de Bézout et de Gauss.

Théorème de Bézout : Soit a et b deux entiers relatifs non nuls et D leur PGCD.Il existe deux entiers relatifs u et v tels que aubv=D . (égalité de Bézout)

Considérons l'ensemble G des entiers naturels non nuls de la forme ambn (avec m et n dans )ℤ

2010@My Maths Space 2/3

Chapitre 2 : PGCD & PPCM TS Spé

Prouver que G est non vide :

Conséquence :

Comparer D et d :

d diviseur commun de a et de b :

Conclusion :

Conséquences: Soit a et b deux entiers relatifs non nuls.

Tout diviseur commun à a et b divise leur PGCD.a et b sont premiers entre eux il existe deux entiers relatifs ⇔ u et v tels que : aubv=1L'équation axby=d ( d entier fixé non nul) admet des solutions entières si et seulement si, d est un multiple de D .

Remarque : Les résolutions d'équations de la forme axby=d font l'objet d'une démarche type qui sera développée plus loin dans ce cours.

Exemple : Montrer que pour tout n , ∈ ℤ 2 n1 et 3n1 sont premiers entre eux.

Théorème de Gauss: Soit a , b et c , trois entiers relatifs non nuls. Si a divise bc et si a et b sont premiers entre eux, alors a divise c .

Exercice : Montrer que si a et b divise un entier c et que a et b sont premiers entre eux alors ab divise c .

Applications : Propriétés du PGCD et du PPCM.Propriétés Soit a et b deux entiers naturels non nuls, D leur PGCD et M leur PPCM .

Il existe deux entiers a ' et b ' premiers entre eux, tels que : a=Da' et b=Db' .

M=Da ' b '=ab '=a ' b et MD=ab .

L'ensemble des diviseurs communs à a et b est l'ensemble des diviseurs de D .

L'ensemble des multiples communs à a et b est l'ensemble des multiples de M .

Exemple : PGCD et PPCM de 1365 et 858.

2010@My Maths Space 3/3