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:
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
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.
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):
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)
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
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!