Pour pouvoir poser une question, vous devez souscrire à un abonnement familial.
Découvrir l'offre
Pour pouvoir accéder à toutes les questions de parents, vous devez souscrire à un abonnement familial.
Découvrir l'offre
Remonter

Maths

Calculer un PGCD et un PPCM

Un PGCD ? Un PPCM ? 

Le calcul d’un PGCD (plus grand diviseur commun) ou d’un PPCM (plus petit multiple commun) de deux nombres peut être utile pour :

Cette fiche explique comment faire.

Calculer un PGCD

Algorithme des soustractions successives

La méthode est la suivante pour calculer le PGCD de deux nombres :

Le mieux est de voir des exemples :

Enoncé

Calculer le PGCD de 108 et de 378.

Réponse 

On applique l’algorithme des soustractions successives (les soustractions sont écrites en vert) :
                 

                   PGCD(378 ; 108)               378 – 108 = 270
                  = PGCD(270 ; 108)            270 – 108 = 162
                  = PGCD(162 ; 108)            162 – 108 = 54
                  = PGCD(108 ; 54)               108 – 54 = 54
                  = PGCD(54 ; 54)                   54 – 54 = 0
                  = 54        

Le PGCD de 108 et de 378 est donc 54.

Enoncé

Calculer PGCD(76 ; 21)

Réponse

On applique l’algorithme des soustractions successives :
                 

                  PGCD(76 ; 21)                       76 – 21 = 55
                  = PGCD(55 ; 21)                   55 – 21 = 34
                  = PGCD(34 ; 21)                   34 – 21 = 13
                  = PGCD(21 ; 13)                   21 – 13 = 8
                  = PGCD(13 ; 8)                     13 – 8 = 5
                  = PGCD(8 ; 5)                        8 – 5 = 3
                  = PGCD(5 ; 3)                        5 – 3 = 2
                  = PGCD(3 ; 2)                        3 – 2 = 1
                  = PGCD(2 ; 1)                        2 – 1 = 1
                  = PGCD(1 ; 1)                        1 – 1 = 0
                  = 1           

Le PGCD de 76 et de 21 est donc 1.

Dans ce cas précis, on dit que 76 et 21 sont « premiers entre eux » : ils n’ont pas de diviseur commun autre que 1.

Algorithme d’Euclide

La lecture est réservée à notre communauté

Vous êtes inscrit ? Identifiez-vous ou inscrivez-vous