Terminale S 2016-2017
Kartable
Terminale S 2016-2017

Rechercher un PGCD

Méthode 1

Par la méthode de l'algorithme d'Euclide

L'algorithme d'Euclide permet de déterminer le PGCD par divisions successives.

Déterminer le PGCD de 214 et de 32.

Etape 1

Poser la division euclidienne du plus grand des deux entiers par le plus petit

On pose la division euclidienne du plus grand des deux entiers par le plus petit.

On pose la division euclidienne de 214 par 32 :

214=32×6+22

Etape 2

Poser les divisions successives des diviseurs par les restes

Si le reste de la précédente division euclidienne n'est pas nul, on pose une nouvelle division euclidienne : celle du diviseur par le reste de la précédente division euclidienne.

Tant que le reste n'est pas nul, on réitère la division du diviseur par le reste.

Veiller à ne pas mélanger les diviseurs et les restes.

Le reste n'étant pas nul, on pose la division euclidienne de 32 par 22 :

32=22×1+10

Le reste n'étant pas nul, on pose la division euclidienne de 22 par 10 :

22=10×2+2

Le reste n'étant pas nul, on pose la division euclidienne de 10 par 2 :

10=2×5+0

Le reste étant nul, on arrête l'algorithme.

Etape 3

Identifier le dernier reste non nul

Dès que l'on obtient une division euclidienne de reste nul, on identifie le reste (non nul) de la division euclidienne précédente : ce nombre est le PGCD des deux entiers initiaux.

L'avant-dernière division euclidienne est :

22=10×2+2

On en conclut que :

PGCD(214;32)=2

Méthode 2

Par la méthode des soustractions successives

L'algorithme des soustractions successives permet également de déterminer le PGCD de deux entiers.

Déterminer le PGCD de 243 et de 165.

Etape 1

Poser la différence du plus grand nombre par le plus petit

On pose la différence du plus grand nombre par le plus petit.

On pose la différence de 243 et de 165 :

243165=78

Etape 2

Poser les soustractions successives

On pose les soustractions successives du résultat obtenu par le plus petit des deux termes de la soustraction précédente. On veille toujours à faire la soustraction du terme le plus grand par le terme le plus petit afin d'avoir un résultat positif.

On réitère la soustraction tant que le résultat n'est pas nul.

Comme le résultat précédent n'est pas nul, on pose la soustraction de 165 par 78 :

16578=87

Comme le résultat précédent n'est pas nul, on pose la soustraction de 87 par 78 :

8778=9

On continue ainsi jusqu'à obtenir un résultat nul :

789=69

699=60

609=51

519=42

429=33

339=24

249=15

159=6

96=3

63=3

33=0

Etape 3

Identifier le dernier résultat non nul

Dès que l'on obtient une soustraction de résultat nul, on identifie le résultat (non nul) de la soustraction précédente : ce nombre est le PGCD des deux entiers initiaux.

L'avant-dernière soustraction est :

63=3

On en conclut que :

PGCD(243;165)=3

La méthode de recherche du PGCD à l'aide des soustractions successives est beaucoup plus longue que celle faisant appel à l'algorithme d'Euclide, on préférera donc cette dernière.

Méthode 3

A l'aide de PGCD(k×a;k×b)=k×PGCD(a;b)

Afin de déterminer un PGCD, on peut utiliser la propriété suivante :

PGCD(k×a;k×b)=k×PGCD(a;b).

Déterminer le PGCD de 170 et de 130.

Etape 1

Déterminer le diviseur commun

On détermine un diviseur commun aux deux nombres.

On remarque que 170 et 130 sont divisibles par 10.

Etape 2

Réciter le cours

On rappelle que :

PGCD(k×a;k×b)=k×PGCD(a;b), avec a, b et k des entiers

On sait que :

PGCD(k×a;k×b)=k×PGCD(a;b), avec a, b et k des entiers

Etape 3

Conclure

On conclut en donnant le PGCD des deux nombres.

On en déduit que :

PGCD(170;130)=PGCD(10×17;10×13)

PGCD(170;130)=10×PGCD(17;13)

Or les nombres 17 et 13 sont premiers entre eux.

On en conclut que :

PGCD(170;130)=10

Méthode 4

Par la décomposition en facteurs premiers

Afin de déterminer le PGCD de deux nombres, on peut les décomposer en produits de facteurs premiers, le PGCD est alors égal au produit des facteurs premiers communs aux deux nombres.

Déterminer le PGCD de 1638 et de 8316.

Etape 1

Décomposer les deux nombres en produits de facteurs premiers

On décompose les deux nombres en produits de facteurs premiers.

On décompose 1638 en produit de facteurs premiers :

1 638=2×819

819=3×273

273=3×91

91=7×13

On en déduit que :

1 638=2×32×7×13

On décompose ensuite 8316 en produit de facteurs premiers :

8 316=2×4 158

4 158=2×2 079

2 079=3×693

693=3×231

231=3×77

77=7×11

On en déduit que :

8 316=22×33×7×11

Etape 2

Identifier les facteurs communs

On identifie le produit de facteurs premiers commun aux deux nombres.

On remarque que 1638 et 8316 ont pour facteur commun 2×32×7.

Etape 3

Conclure

Le PGCD des deux nombres est ainsi le produit des facteurs premiers communs à ces deux nombres.

On en déduit que :

PGCD(8 316;1 638)=2×32×7

Soit :

PGCD(8 316;1 638)=126

pub

Demandez à vos parents de vous abonner

Vous ne possédez pas de carte de crédit et vous voulez vous abonner à Kartable.

Vous pouvez choisir d'envoyer un SMS ou un email à vos parents grâce au champ ci-dessous. Ils recevront un récapitulatif de nos offres et pourront effectuer l'abonnement à votre place directement sur notre site.

J'ai une carte de crédit

Vous utilisez un navigateur non compatible avec notre application. Nous vous conseillons de choisir un autre navigateur pour une expérience optimale.