I. Introduction
On souhaite créer une fonction permettant de calculer le plus grand commun diviseur ou PGCD entre deux nombres entiers à l'aide de l'algorithme d'Euclide.
Ensuite, toujours en se basant sur cet algorithme, on va créer une autre fonction qui pourra déterminer le PGCD de deux polynômes.
II. Définitions mathématiques
II-A. PGCD de nombres entiers
D'après Wikipedia, en mathématiques, le PGCD de nombres entiers différents de zéro est, parmi les diviseurs communs à ces entiers, le plus grand d'entre eux.
Par exemple, les diviseurs positifs de 30 sont, dans l'ordre : 1, 2, 3, 5, 6, 10, 15 et 30. Ceux de 18 sont 1, 2, 3, 6, 9 et 18.
Les diviseurs communs de 30 et 18 étant 1, 2, 3 et 6, leur PGCD est 6. Ce qui se note : PGCD(30, 18) = 6.
Les diviseurs communs à plusieurs entiers sont les diviseurs de leur PGCD. Connaître le PGCD de deux nombres entiers non nuls a et b permet de simplifier la fraction a/b.
Il est possible de le déterminer par divers raisonnements, dont l'algorithme d'Euclide.
II-B. PGCD de polynômes
On va simplement transposer pour les polynômes l'algorithme d'Euclide servant à trouver le PGCD de deux nombres entiers.
Toutefois, comme il y a une infinité de PGCD possibles avec les polynômes, pour avoir un PGCD unique, on choisira par convention le polynôme unitaire, polynôme non nul et dont le coefficient dominant vaut 1.
Connaître le PGCD de deux polynômes non nuls A et B permet de simplifier la fraction A/B.
III. Algorithme d'Euclide
III-A. PGCD de deux nombres entiers
Ainsi, selon Wikipedia, l'algorithme d'Euclide sur deux nombres entiers positifs a et b avec a > b ⩾ 0 procède comme suit :
- si b = 0, l'algorithme termine et rend la valeur a ;
- sinon, l'algorithme calcule le reste r de la division euclidienne de a par b, puis recommence avec a := b et b := r.
Formellement l'algorithme d'Euclide construit une suite finie d'entiers (rn) par récurrence double :
- r0 = a, r1 = b ;
- pour n ⩾ 1, rn+1 est le reste de la division euclidienne de rn-1 par rn, en particulier rn+1 < rn.
La suite (rn) est une suite strictement décroissante d'entiers positifs à partir du rang 1 : elle est donc finie et s'arrête au premier n tel que rn = 0.
Le tableau suivant montre le calcul du PGCD de 21 et 15. On réalise la division euclidienne de a = 21 et b = 15 : le quotient est 1 et le reste 6.
L'algorithme continue avec a := b et b := le précédent reste, jusqu'à trouver un reste nul. L'algorithme s'arrête alors et retourne le dernier reste non nul trouvé, ici r3 = 3 qui est bien le PGCD de 21 et 15 :
III-B. PGCD de polynômes
On procédera de la même façon pour le calcul du PGCD des polynômes A et B :
- si B = 0 alors PGCD(A, B) = A ;
- sinon, l'algorithme calcule le reste R de la division euclidienne des polynômes A et B, puis recommence avec A := B et B := R.
Pour avoir plus d'information sur la division d'un polynôme, je vous invite à consulter la page Division d'un polynôme.
IV. Implémentation en Python
On va chercher comme d'habitude à écrire du code le plus lisible possible, sans chercher forcément à l'optimiser.
IV-A. PGCD de nombres entiers
A partir de l'algorithme décrit précédemment on obtient facilement la fonction récursive :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 | def PGCD(a, b): # si b=0 if (b==0): # renvoi de a return a else: # sinon # calcul du reste r de la division de a par b r = a % b # appel de la fonction PGCD pour a=b et b=r return PGCD(b, r) |
On laisse le choix à chacun de traduire ensuite ce code en fonction itérative.
Testons maintenant cette fonction :
| Code Python : | Sélectionner tout |
1 2 3 4 5 | # calcul du PGCD des entiers 21 et 15 gcd = PGCD(21, 15) # affiche le résultat print("PGCD(21, 15) = " + str(gcd)) |
Le code affiche :
PGCD(21, 15) = 3
IV-B. PGCD de polynômes
On utilise à nouveau notre classe Polynome dans laquelle on va ajouter une méthode pour réaliser une division euclidienne entre deux polynômes :
On donne maintenant le code complet de la méthode permettant de réaliser cette division en surchargeant l'opérateur « / » :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | class Polynome: ... def __truediv__(self, other): # méthode permettant de redéfinir l'opérateur « / » pour 2 polynômes # si le degré de self est inférieur au degré de other if self.degre()<other.degre(): # on renvoie (0, self) : q=0, r=self return (Polynome([0]), self) # sortie de la fonction # polynôme self représentant au départ le reste r r = Polynome(self.coefs) # degré du polynôme représentant le quotient q degre = r.degre() - other.degre() # initialisation du polynôme q : [0, 0, 1] -> ... + X^2 q = Polynome([0]*degre + [1]) # tant que le degré mini des termes du polynôme q est supérieur ou égal à 0, et que r n'est pas égal à 0. while (degre>=0) and (r.coefs[-1]!=0): # coefficient du nouveau terme du polynôme q coef = r.coefs[-1] / other.coefs[-1] # affectation du coefficient au terme q.coefs[degre] = coef # on multiplie le polynôme other par le polynôme coef*(x^degre) p = other * (coef, degre) # soustraction des polynômes r et p r = r - p # degré du nouveau terme du polynôme q degre = r.degre() - other.degre() # renvoi le couple (q, r) représentant le quotient et le reste de la division return (q, r) |
On doit donc d'abord comparer les degrés des polynômes p1 = self et p2 = other au début du code.
Si le degré de p1 est inférieur au degré de p2, alors q = 0 et r = p1,
sinon, on procède à la division des deux polynômes pour obtenir q et r.
Testons cette méthode :
| Code : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 | # création du polynôme p1 = (1 + X)(2 + X) = 2 + 3X + X^2
p1 = Polynome([1, 1])*Polynome([2, 1])
# création du polynôme p2 = 1 + 2X + X^2 = (1 + X)^2
p2 = Polynome([1, 2, 1])
# division euclidienne : p1 = p2*q + r
q, r = p1 / p2
# affiche le quotient q et le reste r de la division
print("q = " + str(q))
print("r = " + str(r)) |
q = 1.0
r = 1.0 + X
On peut maintenant créer notre fonction permettant de déterminer le PGCD entre deux polynômes :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | def PGCD_POLY(A, B): # si B=0 if (B==Polynome([0])): # par convention on choisit de renvoyer le polynôme unitaire, polynôme non nul et dont le coefficient dominant vaut 1 : coef = 1.0/A.coefs[-1] # multiplication de A par coef A = A*(coef,0) # renvoi de A return A else: # détermination du quotient Q et du reste R de la division de A par B Q, R = A / B # appel de la fonction PGCD pour A=B et B=R return PGCD_POLY(B, R) |
Testons enfin notre fonction :
| Code : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 | # création du polynôme p1 = (1 + X)(2 + X) = 2 + 3X + X^2
p1 = Polynome([1, 1])*Polynome([2, 1])
# création du polynôme p2 = 1 + 2X + X^2 = (1 + X)^2
p2 = Polynome([1, 2, 1])
# calcul du PGCD des polynômes p1 et p2
gcd = PGCD_POLY(p1, p2)
# affiche le résultat
print("PGCD(p1, p2) = " + str(gcd)) |
PGCD(p1, p2) = 1.0 + X
IV-C. Application : simplification de fraction
Supposons que l'on souhaite connaître la limite :
On voit facilement qu'on aboutit à une forme indéterminée 0/0.
Pour lever cette indétermination on identifie d'abord le PGCD entre le numérateur et le dénominateur (x - 2), pour ensuite simplifier la fraction :
On obtient ainsi la limite égale à 13/7.
Mise en œuvre en Python :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | # création du polynôme p1 = -10 + X + X^3 p1 = Polynome([-10, 1, 0, 1]) print("p1 = " + str(p1)) # création du polynôme p2 = -6 - X + 2X^2 p2 = Polynome([-6, -1, 2]) print("p2 = " + str(p2)) print() print("Limite de p1/p2 quand X -> 2 = 0/0\n") # calcul du PGCD des polynômes p1 et p2 gcd = PGCD_POLY(p1, p2) # affiche le résultat print("PGCD(p1, p2) = " + str(gcd)) # simplification de p1 p1, r1 = p1 / gcd # simplification de p2 p2, r2 = p2 / gcd print() print("p1/p2 = ({0})/({1})".format(p1, p2)) print() print("Limite de p1/p2 quand X -> 2 = {0}/{1}\n".format(p1.eval(2),p2.eval(2)) |
Le code affiche :
p1 = -10 + X + X^3
p2 = -6 - X + 2.X^2
Limite de p1/p2 quand X -> 2 = 0/0
PGCD(p1, p2) = -2.0 + X
p1/p2 = (5.0 + 2.0.X + X^2)/(3.0 + 2.0.X^1)
Limite de p1/p2 quand X -> 2 = 13.0/7.0
On voit qu'on obtient le même résultat, les termes des polynômes sont simplement affichés dans l'ordre inverse.
IV-D. Module complet
On donne pour finir le code complet permettant d'effectuer les différents tests :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 | class Polynome: def __init__(self, liste_coefs=[0]): # méthode constructeur de la classe # on définit la liste des coefficients du polynôme [a0, a1, ..., an] self.coefs = liste_coefs # suppression si nécessaire des zéros en queue de liste de coefficients. Exemple : [2, 3, 1, 0, 0] -> [2, 3, 1] self.reduire() def __str__(self): # permet d'afficher le polynôme sous la forme 1 + 2x + 3x^2 s="" # initialisation de la chaîne de caractères # on vérifie d’abord si le degré du polynôme est nul if (len(self.coefs)-1==0): return str(self.coefs[0]) else: # sinon if self.coefs[0]!=0: s=str(self.coefs[0]) + " + " for i in range(1, len(self.coefs)): # parcours des indices des coefficients du polynôme : [a1, a2, ..., an] if self.coefs[i]!=0: # si le coefficient de degré i n'est pas nul if self.coefs[i]!=1: # si le coefficient de degré i est différent de 1 s+="{}.X^{} + ".format(self.coefs[i],i) else: s+="X^{} + ".format(i) # élimination des caractères en trop s = s[:-3].replace("+ -", "- ").replace("X^1 ","X ").replace(" 1.X"," X") if s[-2:]=="^1": s = s[:-2] if s[:3]=="1.X": s = s[3:] return s # on retourne l'expression du polynôme def degre(self): # retourne le degré du polynôme return (len(self.coefs)-1) def __add__(self, other): # méthode permettant de redéfinir l'opérateur « + » pour 2 polynômes : (1 + 2x + x^2) + (1 + x) = 2 + 3x + x^2 # p1 = self, p2 = other if len(other.coefs) >len(self.coefs): # si degré de p2 > degré de p1 liste_coefs = other.coefs[:]; n = len(self.coefs) # on copie les coefs du polynôme de degré le plus élevé et la longueur de la liste de coefs la plus petite. else: liste_coefs = self.coefs[:]; n = len(other.coefs) # sinon, ... for i in range(n): # parcours des indices de liste_coefs liste_coefs[i] = self.coefs[i] + other.coefs[i] # addition des coefficients de degré i return Polynome(liste_coefs) # renvoie le polynôme résultat de l'addition def __sub__(self, other): # méthode permettant de redéfinir l'opérateur « + » pour 2 polynômes : (1 + 2x + x^2) + (1 + x) = 2 + 3x + x^2 # p1 = self, p2 = other if len(other.coefs) >len(self.coefs): # si degré de p2 > degré de p1 liste_coefs = other.coefs[:]; n = len(self.coefs) # on copie les coefs du polynôme de degré le plus élevé et la longueur de la liste de coefs la plus petite. else: liste_coefs = self.coefs[:]; n = len(other.coefs) # sinon, ... for i in range(n): # parcours des indices de liste_coefs liste_coefs[i] = self.coefs[i] - other.coefs[i] # addition des coefficients de degré i return Polynome(liste_coefs) # renvoie le polynôme résultat de l'addition def reduire(self): # tant que le dernier élément de la liste est nul while round(self.coefs[-1],12) == 0 and len(self.coefs)>1: self.coefs.pop() # supprimer le dernier élément for i in range(len(self.coefs)): self.coefs[i] = round(self.coefs[i],12) def __mul__(self, other): # méthode permettant de redéfinir l'opérateur « * » pour 2 polynômes : (1 + x) * (1 + 2x) = 1 + 3x + 2x^2 if isinstance(other,tuple): coef = other[0]; degre = other[1] liste_coefs = [0]*degre + self.coefs for i in range(degre, len(liste_coefs)): liste_coefs[i] = liste_coefs[i]*coef else: # initialisation de la liste des coefficients qu'avec des zéros liste_coefs=[0]*(len(self.coefs)+len(other.coefs)-1) # exemple : [0, 0, 0] for i1 in range(len(self.coefs)): # parcours des indices des coefs du polynôme n°1 for i2 in range(len(other.coefs)): # parcours des indices des coefs du polynôme n°2 # multiplication des coefficients d'indices i1 et i2 liste_coefs[i1+i2] = liste_coefs[i1+i2] + self.coefs[i1]*other.coefs[i2] poly = Polynome(liste_coefs) # création de l'objet Polynome basé sur la liste return poly # renvoie le polynôme résultat de la multiplication def __pow__(self, n): # méthode permettant de redéfinir l'opérateur de puissance : self ** n # on crée l'objet poly à partir d'une liste contenant un seul élément 1, élément neutre pour la multiplication des polynômes poly = Polynome([1]) for i in range(n): # on multiplie n fois poly par self à l'aide de l'opérateur * poly = poly*self # équivalent à : poly = poly.__mul__(self) return poly # renvoie le polynôme résultat de l'opération (self ** n) def __truediv__(self, other): # méthode permettant de redéfinir l'opérateur « / » pour 2 polynômes # si le degré de self est inférieur au degré de other if self.degre()<other.degre(): # on renvoie (0, self) : q=0, r=self return (Polynome([0]), self) # sortie de la fonction # polynôme self représentant au départ le reste r r = Polynome(self.coefs) # degré du polynôme représentant le quotient q degre = r.degre() - other.degre() # initialisation du polynôme q : [0, 0, 1] -> ... + X^2 q = Polynome([0]*degre + [1]) # tant que le degré mini des termes du polynôme q est supérieur ou égal à 0, et que r n'est pas égal à 0. while (degre>=0) and (r.coefs[-1]!=0): # coefficient du nouveau terme du polynôme q coef = r.coefs[-1] / other.coefs[-1] # affectation du coefficient au terme q.coefs[degre] = coef # on multiplie le polynôme other par le polynôme coef*(x^degre) p = other * (coef, degre) # soustraction des polynômes r et p r = r - p # degré du nouveau terme du polynôme q degre = r.degre() - other.degre() # renvoi le couple (q, r) représentant le quotient et le reste de la division return (q, r) def __eq__(poly1, other): # méthode permettant de redéfinir l'opérateur « == » pour 2 polynômes return (poly1.coefs==other.coefs) # renvoie True si les 2 listes de coefficients sont égales def eval(self,x): # méthode permettant d'évaluer le polynôme en fonction de x # intialisation des variables valeur_polynome = self.coefs[0] # valeur_polynome = a0 power=1 for coef in self.coefs[1:]: # parcours des coefficients du polynôme à partir de a1 : a1, a2, ..., an power = power*x # calcul de la puissance de x pour ai : power = x^i valeur_polynome += coef*power # valeur_polynome = valeur_polynome + ai*x^i return valeur_polynome # renvoie la valeur du polynôme def eval_horner(self,x): # méthode permettant d'évaluer le polynôme en fonction de x # intialisation de la variable valeur_polynome = self.coefs[-1] # valeur_polynome = an for coef in reversed(self.coefs[:-1]): # parcours des coefficients du polynôme à partir de an-1 : an-1, ..., a1, a0 valeur_polynome = valeur_polynome*x + coef # valeur_polynome = valeur_polynome*x + ai return valeur_polynome # renvoie la valeur du polynôme def PGCD(a, b): # si b=0 if (b==0): # renvoi de a return a else: # sinon # calcul du reste r de la division de a par b r = a % b # appel de la fonction PGCD pour a=b et b=r return PGCD(b, r) def PGCD_POLY(A, B): # si B=0 if (B==Polynome([0])): # par convention on choisit de renvoyer le polynôme unitaire, polynôme non nul et dont le coefficient dominant vaut 1 : coef = 1/A.coefs[-1] # multiplication de A par coef A = A*(coef,0) # renvoi de A return A else: # détermination du quotient Q et du reste R de la division de A par B Q, R = A / B # appel de la fonction PGCD pour A=B et B=R return PGCD_POLY(B, R) print("I. PGCD de deux entiers :\n") # calcul du PGCD des entiers 25 et 15 gcd = PGCD(21, 15) # affiche le résultat print("PGCD(21, 15) = " + str(gcd)) print();print() print("II. Division de deux polynômes :\n") # création du polynôme p1 = (1 + X)(2 + X) = 2 + 3X + X^2 p1 = Polynome([1,1])*Polynome([2, 1]) print("p1 = " + str(p1)) # création du polynôme p2 = 1 + 2X + X^2 = (1 + X)^2 p2 = Polynome([1, 2, 1]) print("p2 = " + str(p2)) print() # division euclidienne : p1 = p2*q + r q, r = p1 / p2 # affiche le quotient q et le reste r de la division print("q = " + str(q)) print("r = " + str(r)) print();print() print("III. PGCD de deux polynômes :\n") # calcul du PGCD des polynômes p1 et p2 gcd = PGCD_POLY(p1, p2) # affiche le résultat print("PGCD(p1, p2) = " + str(gcd)) print();print() print("IV. Application : simplification de fractions :\n") # création du polynôme p1 = -10 + X + X^3 p1 = Polynome([-10, 1, 0, 1]) print("p1 = " + str(p1)) # création du polynôme p2 = -6 - X + 2X^2 p2 = Polynome([-6, -1, 2]) print("p2 = " + str(p2)) print() print("Limite de p1/p2 quand X -> 2 = 0/0\n") # calcul du PGCD des polynômes p1 et p2 gcd = PGCD_POLY(p1, p2) # affiche le résultat print("PGCD(p1, p2) = " + str(gcd)) # simplification de p1 p1, r1 = p1 / gcd # simplification de p2 p2, r2 = p2 / gcd print() print("p1/p2 = ({0})/({1})".format(p1, p2)) print() print("Limite de p1/p2 quand X -> 2 = {0}/{1}\n".format(p1.eval(2),p2.eval(2))) |
V. Conclusion
Après avoir décrit l'algorithme d'Euclide, nous avons pu créer des fonctions récursives permettant d'obtenir le PGCD de deux nombres entiers et celui de deux polynômes.
Chacun pourra ensuite librement les transformer en fonctions itératives.
Sources :
https://fr.wikipedia.org/wiki/Plus_g...ombres_entiers
https://fr.wikipedia.org/wiki/Plus_g...ommun_diviseur
https://fr.wikipedia.org/wiki/Algorithme_d%27Euclide
https://fr.wikipedia.org/wiki/Divisi..._polyn%C3%B4me
https://fr.wikipedia.org/wiki/Polyn%C3%B4me_unitaire
http://www.jybaudot.fr/Maths/divipolyn.html