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 entiers positifs

Définition

Parmi les diviseurs communs de deux entiers non nuls a et b, il y en a toujours un plus grand, noté pgcd(a, b).

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 entiers par divisions euclidiennes successives.

Propriété de transmission du PGCD

Propriété

Soient $a,b,q,r$ quatre 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 entiers non nuls sont premiers entre eux si et seulement si leur PGCD vaut 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 dite 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 suffit de simplifier par le PGCD du numérateur et du dénominateur, ou bien de simplifier par des diviseurs communs tant qu'il en reste.

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