User

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 (r_n) par récurrence double :

• r₀ = a, r₁ = b ;
• pour n ⩾ 1, r_n+1 est le reste de la division euclidienne de r_n-1 par r_n, en particulier r_n+1 < r_n.

La suite (r_n) 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 r_n = 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 r₃ = 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 - Visualiser dans une fenêtre à part

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 - Visualiser dans une fenêtre à part

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 - Visualiser dans une fenêtre à part

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 - Visualiser dans une fenêtre à part

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))

Le code affiche le quotient q et le reste r résultat de la division :

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 - Visualiser dans une fenêtre à part

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 - Visualiser dans une fenêtre à part

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))

Le code affiche :

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 - Visualiser dans une fenêtre à part

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 - Visualiser dans une fenêtre à part

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