Introduction

Le plus grand commun diviseur, aussi connu sous le nom de PGCD, est nécessaire pour de nombreuses applications comme la simplification de fractions ou encore déterminer si deux nombres sont premiers entre eux. Étudions ses propriétés et ses différentes applications.

Rappel sur le PGCD

Qu'est ce que le PGCD ? Rappelons ce qu'est le PGCD et ce qui a été vu dans au collège le concernant.

Soient a et b des entiers positifs.

On a vu en classe de 3ème que le PGCD de deux nombres a et b est le plus grand nombre qui divise à la fois a et b. Par exemple, le PGCD de 15 et 10 est 5. Pour déterminer le PGCD de deux nombres, on peut faire une liste des diviseurs de a puis de b et déterminer le plus grand diviseur commun.

Lorsque les nombres sont grands, on peut utiliser la factorisation en nombre premier pour déterminer le PGCD. Par exemple,

    \[36=9\times 4=3^2\times 2^2\]

et

    \[60=6\times10=2^2\times3\times5\]

On a alors

    \[PGCD(36,60)=2^2\times 3=12\]

Le calcul du PGCD sert notamment pour rendre une fraction irréductible. Pour cela, il faut calculer le PGCD du numérateur et du dénominateur puis diviser l'ensemble de la fraction par le PGCD obtenu.

Par exemple, pour simplifier la fraction

    \[\frac{312}{845}\]

on calcule le PGCD de 312 et 845 puis on divise le numérateur et le dénominateur de la fraction par ce PGCD. On a

    \[312=2\times156=2^2\times78=2^3\times39\]

    \[=2^3\times3\times13\]

et

    \[845=5\times169=5\times13^2\]

Donc le PGCD de 312 et 845 est 13. Ainsi on divise le numérateur et le dénominateur par 13, ce qui donne

    \[\frac{312}{845}=\frac{24}{65}\]

.

 

Définitions et propriétés du PGCD

Qu'est ce qu'un diviseur ? Définissons maintenant plus précisément le PGCD et découvrons les propriétés qui l'entoure.

Étudions maintenant de façon plus précise ce que représente le PGCD.

On note D(a) l'ensemble des diviseurs de a. Les éléments de D(a) sont tous inférieurs ou égaux à a. Lorsque a>1, D(a) contient au moins 1 et a. Le plus grand élément de D(a) est a et son plus petit est 1.

On note D(a,b) les diviseurs communs à a et à b. D(a,b) est l'intersection de D(a) et D(b). De plus, D(a,b)=D(b,a).

D(a,b) n'est pas vide puisqu'il contient 1. Tous ses éléments sont inférieurs ou égaux à a et inférieurs ou égaux à b. Donc D(a,b) contient un plus grand élément qui est appelé le PGCD.

Par exemple, on veut déterminer PGCD(6,15). D(6)={1,2,3,6} et D(15)={1,3,5,15}. Donc D(6,15)={1,3}. Ainsi, PGCD(6,15)=3.

Lorsque le PGCD vaut 1, on dit que a et b sont premiers entre eux.

Si b divise a, b différent de 0, alors tout diviseur de b divise aussi a d'où D(b) est inclus dans D(a). Ainsi, D(a,b)=D(b) et PGCD(a,b)=b.

Tout diviseur de deux entiers a et b est un diviseur de leur PGCD et réciproquement.

Un première méthode envisageable pour déterminer le PGCD est par soustractions successives. En effet, on a D(a,b)=D(b,a-b) où a>b. Montrons le. Montrons d'abord que si d appartient à D(a,b) alors d appartient à D(b,a-b). Si d appartient à D(a,b) alors d divise a et d divise b alors d divise b et d divise a-b. Donc d appartient à D(b,a-b). Montrons maintenant que si d appartient à D(b,a-b) alors d appartient à D(a,b). Si d appartient à D(b,a-b) alors d divise b et d divise a-b d'où d divise (a-b+b)=a. Donc d divise b et d divise a. Donc d appartient à D(a,b).

Cherchons le PGCD de 168 et 264. D(264,168)=D(168,264-168)=D(168,96)=D(96,168-96)=D(96,72)=D(72,96-72)=D(72,24)=D(24,72-24)=D(24,48)=D(24,48-24)=D(24,24)=D(24). Donc PGCD(264,168)=24.

 

L'algorithme d'Euclide

Qu'est ce que l'algorithme d'Euclide ? Comment déterminer le PGCD ? Grace à l'algorithme d'Euclide, méthode qui fonctionne à tous les coups !

L'algorithme d'Euclide est une autre méthode pour calculer le PGCD de deux nombres : par divisions successives. Cette méthode consiste à exprimer d'abord le plus grand nombre en fonction du plus petit et d'un reste. Puis on exprime le plus petit en fonction du précédent reste et d'un nouveau reste. On continue ce procédé jusqu'à ce que l'on arrive à un reste nul. Le dernier reste non nul est alors le PGCD des deux nombres de départ.

Cette méthode est basée sur le fait que D(a,b)=D(b,r) où a=bq+r est la division euclidienne de a par b. Montrons le. Si d appartient à D(a,b) alors d divise a et d divise b alors d divise a et d divise b et d divise bq. Donc d divise b et d divise a-bq d'où d appartient à D(b,r). Donc D(a,b) est inclus dans D(b,r). Réciproquement, si d appartient à D(b,r) alors d divise b et d divise r. Donc d divise b et d divise a-bq d'où d divise b et d divise bq et d divise a+bq-bq=a. Ainsi d divise b et d divise a d'où d appartient à D(a,b). Donc D(b,r) est inclus dans D(a,b). En conclusion, D(a,b)=D(b,r).

Si r=0, alors b divise a et D(a,b)=D(b).

Prenons un exemple, calculons le PGCD de 144 et 840.

    \[840=144\times5+120\]

D(840,144)=D(144,120)

    \[144=120\times1+24\]

D(144,120)=D(120,24)

    \[120=24\times5+0\]

D(120,24)=D(24,0)=D(24).

Donc PGCD(840,144)=24 puisque 24 est le dernier reste non nul.

Prenons un deuxième exemple en calculons le PGCD de 421 et 189.

    \[421=189\times2+43\]

    \[189=43\times4+17\]

    \[43=17\times2+9\]

    \[17=9\times1+8\]

    \[9=8\times1+1\]

    \[8=1\times8+0\]

Le dernier reste non nul est 1 donc PGCD(421,189)=1. Donc 421 et 189 sont premiers entre eux.

 

Exercices sur le PGCD

Comment déterminer le PGCD de deux nombres ? Passons maintenant à quelques exercices pour apprendre à déterminer le PGCD de deux nombres et déterminer s'ils sont premiers entre eux.

Exercice 1

Déterminer, à l'aide de la factorisation en nombres premiers, le PGCD de 56 et 24, le PGCD de 47 et 95, le PGCD de 126 et 42 et le PGCD de 452 et 289.

Exprimons les résultats dans le tableau ci-dessous :

 factorisation du premier nombrefactorisation du deuxième nombrePGCD
PGCD(56,24)56=2³x724=2³x32³=8
PGCD(47,95)47 est un nombre premier95=5x191
PGCD(126,42)126=2x7x3²42=2x3x72x7x3=42
PGCD(452,289)452=2²x113289=17²1

Exercice 2

Déterminer, à l'aide de l'algorithme d'Euclide, le PGCD de 145 et 127, le PGCD de 39 et 24, le PGCD de 265 et 487 et le PGCD de 327 et 642.

Donnons les résultats dans un tableau :

 Etape 1Etape 2Etape 3Etape 4Etape 5PGCD=dernier reste non nul
PGCD(145,127)145=127x1+18127=18x7+118=1x18+01
PGCD(39,24)39=24x1+1524=15x1+915=9x1+69=6x1+36=3x2+03
PGCD(265,487)487=265x1+222265=222x1+43222=43x5+743=7x6+17=1x7+01
PGCD(327,642)642=327x1+315327=315+12315=12x26+312=3x4+03

Exercice 3

Quelle méthode utiliser pour calculer le PGCD ? Terminons avec un dernier exercice d'application, cette fois ci dans un problème concret.

Le calcul du PGCD peut servir pour résoudre certains problèmes. Par exemple, prenons le problème suivant :

Un commerçant reçoit 90 lampes de poches avec 135 ampoules et qu'il veut vendre des lots identiques sans qu'il ne lui reste d'ampoule ni de lampe. On peut se demander combien il devra mettre d'ampoules et de lampes dans chaque lot afin d'obtenir le plus de lot possible.

Le nombre de lots doit être un diviseur de 90 et également un diviseur de 135. On ne peut diviser le nombre d'ampoule ou de lampes que par un nombre entier et il ne doit rester ni lampe ni ampoule au commerçant. Pour obtenir le maximum de lots, il doit diviser 90 et 135 par le plus grand nombre possible. Il doit donc chercher le PGCD de 90 et de 135. On peut appliquer l'algorithme d'Euclide :

    \[135=90\times1+45\]

    \[90=42\times2+0\]

Donc PGCD(135,90)=45 et le commerçant peut faire un maximum de 45 lots contenants chacun 2 lampes (90 divisé par 45) et 3 ampoules (135 divisé par 45).

Besoin d'un professeur de Maths ?

Vous avez aimé l’article ?

Aucune information ? Sérieusement ?Ok, nous tacherons de faire mieux pour le prochainLa moyenne, ouf ! Pas mieux ?Merci. Posez vos questions dans les commentaires.Un plaisir de vous aider ! :) 3,50/5 - 2 vote(s)
Loading...

Elise

Freelancer, superprof et étudiante en mathématiques, je souhaite partager et étendre mes connaissances grâce à vous !