Le P.G.C.D.

Le Plus Grand Diviseur Commun (PGCD) de deux nombres correspond à la valeur la plus grande commune entre eux. Le PGCD permet de réduire des fractions et de résoudre certains problèmes de comparaisons de quantités par exemple.

Un nombre divise un autre nombre si le résultat de la division est un nombre entier.

Par exemple, 7 divise 21 car 21 / 7 = 3. De même, 12 est un diviseur de 144 car 144 / 12 = 12. Le reste de chaque division est nul. Le chiffre 7 n'est par contre pas un diviseur de 22 car 22 / 7 = 3,1428 (approché au 4e chiffre après la virgule).

Pour trouver le PGCD de deux nombres, plusieurs méthodes existent.

Méthode par liste de diviseurs

Cela revient à décomposer chaque nombre en la suite de ses diviseurs et à prendre la plus petite combinaison de chiffres communs des deux. Par exemple, la liste des diviseurs de 132 = 2, 2, 3, 11 (132 = 2 x 2 x 3 x 11) et celle de 72 = 2, 2, 2, 3, 3 (72 = 2 x 2 x 2 x 3 x 3). Ainsi le PGCD entre 132 et 72 revient à prendre la plus petite combinaison de chiffres communs entre les deux, à savoir 2 x 2 x 3 = 12.

Méthode d'Euclide

Lorsque les nombres sont grands (supérieurs à 100), la liste de diviseurs peut être longue. Nous nous tournerons alors vers la méthode d'Euclide qui consiste à réaliser des divisions successives basées sur la représentation d'une division par un quotient multiplié par le dénominateur et le reste de la division : a / b = q x b + r.
La succession de divisions à faire est la suivante :

• On commence par exprimer la division par la somme d'une multiplication et du reste.
• On affecte le dénominateur au numérateur et le reste devient le quotient.
• On recommence jusqu'à ce que la division donne un reste nul.
• Le PGCD est alors le dernier reste non nul.

Par exemple, cherchons le PGCD de 132 et 72 comme tout à l'heure :

• 132 / 72 = 72 x 1 + 60
• 72 / 60 = 60 x 1 + 12
• 60 / 12 = 12 x 5 + 0

Dans ce cas, le dernier reste non nul est 12 = PGCD(132, 72).

Exemple par la méthode d'Euclide

def pgcd(a, b):
   if a < b:
      b, a = a, b

   r = 1
   while r > 0:
      q = int(a / b)
      r = int(a % b)

      a = b
      b = r

   return (a, b)


print(pgcd(132, 72))
print(pgcd(60, 36))
print(pgcd(2967, 798))
print(pgcd(45, 18))
print(pgcd(58, 34))

Le P.P.C.M.

Le Plus Petit Commun Multiple (PPCM) de deux nombres correspond à l'ensemble des facteurs premiers apparaissant dans chaque décomposition des nombres, en prenant la puissance la plus importante à chaque fois...Ouf...Pas simple. Une chose remarquable est que PGCD(a, b) * PPCM(a, b) = a * b.

Pour trouver le PPCM de deux nombres, nous pouvons chercher leur PGCD et diviser a * b par le PGCD. Nous ne ferons pas de démonstration en ce sens.

L'autre solution consiste en la décomposition en facteurs premiers et à prendre la puissance de chacun de ces facteurs apparaissant en commun dans chaque décomposition.

Par exemple, si l'on cherche le PPCM(132, 72) nous allons décomposer les deux nombres en facteurs premiers :

• 132 = 2 * 2 * 3 * 11
• 72 = 2 * 2 * 2 * 3 * 3

Les facteurs en commun sont 2, 3 et 11. Si l'on compte le nombre d'occurrences de chacun nous voyons 2 * 2 * 2 * 3 * 3 * 11 = 792.

Pour vérifier, nous savons que PGCD(132, 72) = 12 (voir le paragraphe sur le PGCD ci-dessus) et que PPCM(132, 72) = 792. D'après le théorème stipulant que a * b = PPCM(a, b) * PGCD(a, b) alors nous avons 132 * 72 = 792 * 12

Il n'y a pas d'exemple de code particulier car il suffit de prendre le PGCD des nombres et de le diviser par la multiplication des nombres.