Outils pour utilisateurs

Outils du site


pgcd_ppcm

Calcul des PGCD et PPCM

Calcul du PGCD de 2 nombres entiers

PGCD = Plus Grand Commun Diviseur

Voir définition sur Wikipedia: http://fr.wikipedia.org/wiki/PGCD

Regardons ce que donne le décomposition en facteurs premiers de l'exemple de wikipedia:

facteurs(42) => [2,3,7]
facteurs(56) => [2,2,2,7]

On voit bien que les facteurs premiers communs aux deux sont: 2 et 7. On a donc bien PGCD = 2*7 = 14.

Ce que donne bien les fonctions proposées ci-dessous:

pgcd(56,42) => 14

Utilisation pratique (entre autres): simplification d'une fraction.

Pour le calcul, on utilise l'algorithme d'Euclide. Voir ici: http://fr.wikipedia.org/wiki/Algorithme_d%27Euclide.

Prenons un exemple de calcul à la main: le calcul du PGCD de a=56 et b=42:

  • 1- reste de la division entière de a=56 par b=42 ⇒ r=14
  • 2- on fait a=b=42 et b=r=14
  • 3- reste de la division entière de a=42 par b=14 ⇒ r=0
  • 4- Comme le reste r est nul, on en déduit que le PGCD est b=14.

Simple, non ? (merci Euclide!)

Codage du PGCD en version récursive:

#!/usr/bin/python
# -*- coding: utf-8 -*-
 
def pgcd(a,b):
    """pgcd(a,b): calcul du 'Plus Grand Commun Diviseur' entre les 2 nombres entiers a et b"""
    if b==0:
        return a
    else:
        r=a%b
        return pgcd(b,r)
 
# Exemple d'utilisation:
print pgcd(56,42) # =>  affiche 14

Codage du PGCD dans sa version non-récursive (à cause des limites de la pile Python):

#!/usr/bin/python
# -*- coding: utf-8 -*-
 
def pgcd(a,b):
    """pgcd(a,b): calcul du 'Plus Grand Commun Diviseur' entre les 2 nombres entiers a et b"""
    while b<>0:
        r=a%b
        a,b=b,r
    return a
 
# Exemple d'utilisation:
print pgcd(56,42) # =>  affiche 14

Et, avec Python, on peut encore simplifier en éliminant la variable intermédiaire r, grâce au fait que dans l'expression a,b=b,r toutes les évaluations sont faites avant les affectations. On peut donc écrire tout simplement:

def pgcd(a,b):
    """pgcd(a,b): calcul du 'Plus Grand Commun Diviseur' entre les 2 nombres entiers a et b"""
    while b<>0:
        a,b=b,a%b
    return a

Il est difficile de faire plus simple!

Cas particuliers conformes à la définition mathématique (mais sans sens concret):

pgcd(56,0) => 56
pgcd(0,42) => 42
pgcd(0,0) => 0

Calcul du PGCD de n (>=2) nombres entiers

Une curiosité: calcul du PGCD d'un nombre quelconque d'entiers.

Il suffit de calculer le PGCD de 2 nombres et de l'intégrer dans un nouveau calcul avec le nombre suivant.

Par exemple avec 3 nombres: le PGCD de a, b et c: pgcd(pgcd(a,b),c)

On peut facilement généraliser à n valeurs.

Cela donne, par exemple, le code suivant:

def pgcdn(*n):
    """Calcul du 'Plus Grand Commun Diviseur' de n valeurs entières (Euclide)"""
    p = pgcd(n[0], n[1])
    for x in n[2:]:
        p = pgcd(p, x)
    return p

Exemple d'utilisation:

a = 30   # 2*3*5
b = 462  # 2*3*7*11
c = 390  # 2*3*5*13
d = 798  # 2*3*7*19
 
print pgcdn(a, b, c, d)
6

En effet, 2*3=6 est bien le PGCD des 4 nombres a, b, c et d.

En fait, on peut proposer cet autre code plus compact et surtout autonome comme seule fonction pgcd() valable pour n'importe quel nombre de paramètres à partir de 2:

def pgcd(*n):
    """Calcul du 'Plus Grand Commun Diviseur' de n (>=2) valeurs entières (Euclide)"""
    def _pgcd(a,b):
        while b: a, b = b, a%b
        return a
    p = _pgcd(n[0], n[1])
    for x in n[2:]:
        p = _pgcd(p, x)
    return p

Et avec ça, vous pouvez calculer:

a = 2*5*7 # 70
b = 2*7*11 # 154
c = 2*3*5*7 # 210
d = 2*3*11 # 66
 
print pgcd(a, b)
14
print pgcd(a, b, c)
14
print pgcd(a, b, c, d)
2

On voit bien que 2*7=14 sont les facteurs communs de a, b et c, mais que d n'a plus que le facteur 2 en commun avec les 3 autres.

Calcul du PGCD étendu avec les coefficients de Bézout et l'inversion modulaire

Pour la théorie, voir ici: http://fr.wikipedia.org/wiki/Algorithme_d%27Euclide_%C3%A9tendu

Les résultats supplémentaires sont utilisés en arithmétique modulaire, et en particulier en cryptologie.

La fonction, toujours basée sur Euclide, mais ici étendu, donne, en plus du PGCD de a et b, les 2 coefficients de bézout tels que a*u + b*v = pgcd(a, b)

→ voir le théorème de Bachet-Bézout (http://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Bachet-B%C3%A9zout)

De plus, si a et b sont premiers entre eux (donc pgcd(a,b)=1):

  • u correspond à l'inverse modulaire de a modulo b
  • et v celui de b modulo a.

Voilà le code proposé:

def pgcde(a, b):
    """ pgcd étendu avec les 2 coefficients de bézout u et v
        Entrée : a, b entiers
        Sorties : r = pgcd(a,b) et u, v entiers tels que a*u + b*v = r
    """
    r, u, v = a, 1, 0
    rp, up, vp = b, 0, 1
    while rp != 0:
        q = r//rp
        rs, us, vs = r, u, v
        r, u, v = rp, up, vp
        rp, up, vp = (rs - q*rp), (us - q*up), (vs - q*vp)
    return (r, u, v)

Exemple d'utilisation:

a = 120 b = 23

p, u, v = pgcde(a, b)

donne: p=1 u=-9 et v=47

On vérifie bien que a*u + b*v = pgcd(a,b): 120*(-9)+23*47=1

p=1 signifie que a et b sont premiers entre eux (= n'ont aucun facteur premier en commun)

On a donc: u est l'inverse de a modulo b: a*u = 1 mod b => (120*(-9))%23 = 1

On a aussi: v est l'inverse de b modulo a: b*v = 1 mod a => (23*47)%120 = 1

Quand on ne cherche que l'inverse modulaire de a, on peut alléger les calculs en supprimant le calcul de v, puisque u et v sont calculés séparément.

On peut toujours calculer v après: v = (p-a*u)//b. Avec les nombres cités en exemple ci-dessus, on a bien (1-120*(-9))//23 = 47

Voilà le code:

def pgcdi(a, b):
    """ pgcd étendu avec le 1er coef de bézout (pour inversion modulaire de a)
        Entrée : a, b entiers
        Sorties : p = pgcd(a,b) et u tels que a*u + b*v = p
           v peut être déduit par calcul: v = (p-a*u)//b
    """
    r, u = a, 1
    rp, up = b, 0
    while rp != 0:
        q = r//rp
        rs, us = r, u
        r, u = rp, up
        rp, up = (rs - q*rp), (us - q*up)
    return (r, u)

Calcul du PPCM de 2 nombres entiers

PPCM = Plus Petit Commun Multiple

Voir définition sur Wikipedia: http://fr.wikipedia.org/wiki/PPCM

Reprenons l'exemple utilisé plus haut pour le PGCD:

Décomposition en facteurs premiers de 56 et 42:

facteurs(56) => [2,2,2,7]
facteurs(42) => [2,3,7]

Pour calculer le PPCM, on multiplie tous les facteurs trouvés, et quand un facteur a été trouvé dans les 2 nombres, on le prend avec l'exposant le plus grand:

(2**3)*3*7 => 168

Et la fonction donnée ci-dessous donne bien:

ppcm(42,56) => 168

Si vous avez bien analysé ce qu'on a fait, vous trouvez vous-même la relation entre le PPCM et le PGCD:

(PPCM de a et b) = a*b / (PGCD de a et b).

Et comme nous avons une fonction rapide (grâce à Euclide) pour calculer le PGCD, nous allons l'utiliser pour le PPCM!

#!/usr/bin/python
# -*- coding: utf-8 -*-
 
def ppcm(a,b):
    """ppcm(a,b): calcul du 'Plus Petit Commun Multiple' entre 2 nombres entiers a et b"""
    if (a==0) or (b==0):
        return 0
    else:
        return (a*b)//pgcd(a,b)
 
# exemple d'utilisation:
print ppcm(56,42) # => affiche 168

Il est difficile de faire plus simple, non?

Cas particulier conformes à la définition mathématique (mais sans sens concret):

ppcm(56,0) => 0
ppcm(0,42) => 0
ppcm(0,0) => 0 

Calcul du PPCM de n (>=2) nombre entiers

On va faire comme pour le PGCD: ppcm(a, b, c) = ppcm(ppcm(a, b), c)

Voilà un code autonome qui fera ça très bien, et qui s'appuie sur le pgcd d'Euclide:

def ppcm(*n):
    """Calcul du 'Plus Petit Commun Multiple' de n (>=2) valeurs entières (Euclide)"""
    def _pgcd(a,b):
        while b: a, b = b, a%b
        return a
    p = abs(n[0]*n[1])//_pgcd(n[0], n[1])
    for x in n[2:]:
        p = abs(p*x)//_pgcd(p, x)
    return p

Application:

a = 2*5*7 # 70
b = 2*7*11 # 154
c = 2*3*5*7 # 210
d = 2*3*11 # 66
 
print ppcm(a, b)
770
print ppcm(a, b, c)
2310
print ppcm(a, b, c, d)
2310


Amusez-vous bien!

pgcd_ppcm.txt · Dernière modification: 2009/11/23 17:57 de tyrtamos

Outils de la page