Initiation à l'arithmétique/PGCD

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Plus grand diviseur commun de deux nombres entiers positifs

Définition

Soient deux nombres entiers non nuls a et b. Le plus grand diviseur commun de ces deux nombres s'appelle PGCD et se note $pgcd(a,b)$.

Il s'agit du plus grand nombre entier par lequel a et b sont divisibles.

Début de l'exemple

Exemple : pgcd(24, 36)

Les diviseurs de 24 sont 1, 2, 3, 4, 6, 8, 12 et 24.

Les diviseurs de 36 sont 1, 2, 3, 4, 6, 9, 12, 18 et 36.

Les diviseurs communs de 24 et 36 sont 1, 2, 3, 4, 6 et 12.

Donc le plus grand diviseur commun de 24 et 36 est pgcd(24, 36) = 12.

Fin de l'exemple

Algorithme d’Euclide : une méthode pour trouver le PGCD

Le mot algorithme vient du mathématicien arabe du XI^e siècle Al-Khwarizmi.

Euclide est un savant grec du III^e siècle avant J.C., auteur des fameux Éléments.

Un algorithme est une procédure automatisée qui permet de trouver un résultat « sans réfléchir ». Par exemple, quand on pose une opération, on applique un algorithme.

L'algorithme d'Euclide est une méthode pour trouver le PGCD de deux nombres entiers par divisions euclidiennes successives.

Propriété de transmission du PGCD

Propriété

Soient $a,b,q,r$ quatre nombres entiers non nuls.

Si $a=b\times q+r$, alors $\operatorname {pgcd} (a,b)=\operatorname {pgcd} (b,r)$.

Début de l'exemple

Exemple

$49=14\times 3+7$.

$\operatorname {pgcd} (49,14)=\operatorname {pgcd} (14,7)=7$.

Fin de l'exemple

Algorithme d’Euclide : exemple

On veut le PGCD de $702$ et $273$.

On effectue les divisions successives :

$702=273\times 2+156$ ;

$273=156\times 1+117$ ;

$156=117\times 1+39$ ;

$117=39\times 3+0$.

Le dernier reste non nul est $39$ donc $\operatorname {pgcd} (702,273)=39$.

Applications du PGCD

Nombres premiers entre eux

Définition

Définition

Deux entiers sont dits premiers entre eux si leurs seuls diviseurs communs sont 1 et –1.

PGCD de deux nombres premiers entre eux

Propriété

Deux nombres entiers non nuls sont premiers entre eux si et seulement si leur PGCD est égal à 1.

Exemple

25 et 36 sont premiers entre eux (bien qu’aucun des deux ne soit premier !) car leur PGCD vaut 1.

Contre-exemple

24 et 36 ne sont pas premiers entre eux, car leur PGCD vaut 12 (leurs diviseurs communs sont donc : 1, 2, 3, 4, 6, 12).

Rendre une fraction irréductible

Définition

Une fraction est irréductible si le numérateur (en haut) et le dénominateur (en bas) sont premiers entre eux.

Méthode

Pour rendre une fraction irréductible, il faut la simplifier par le PGCD du numérateur et du dénominateur.

Début de l'exemple

Exemple

Pour rendre irréductible la fraction ${\frac {75}{60}}$ :

• calculons, avec l'algorithme d'Euclide, le PGCD de $75$ et $60$.

  $75=60\times 1+15$

  $60=15\times 4+0$

  donc $\operatorname {pgcd} (75,60)=15$

  donc ${\frac {75}{60}}={\frac {5\times 15}{4\times 15}}={\frac {5}{4}}$

  et cette dernière fraction est irréductible.

• ou bien simplifions successivement par les diviseurs communs évidents :

  ${\frac {75}{60}}={\frac {5\times 15}{5\times 12}}={\frac {15}{12}}$

  ${\frac {15}{12}}={\frac {3\times 5}{3\times 4}}={\frac {5}{4}}$.

Fin de l'exemple