ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

↓

Division polynomiale, pgcd de deux polynômes     » PGCD | Division selon les puissances croissantes & application aux développements limités          Cas particulier de la division par x - a, recherche de l'équation d'une asymptote "oblique"

↑

Soit K[x] l'ensemble des polynômes de la variable réelle ou complexe x (K = R ou C). Muni de l'addition et de la multiplication des fonctions, ces polynômes constituent un anneau unitaire, x → 1 est neutre pour la multiplication, son élément nul, neutre pour l'addition est le polynôme nul,  x → 0. Cet anneau est intègre : le produit de deux polynômes non nuls ne peut être nul à moins que l'un des deux soit nul.

Soit B un polynôme non nul; à l'instar de l'arithmétique dans Z, on dit que A et C sont congrus modulo B pour exprimer qu'il existe un polynôme Q tel que : A - C = BQ, polynôme produit de B par Q et on écrit A ≡ C mod.B

∗∗∗
Montrer que l'on définit ainsi une relation d'équivalence dans K[x]

• Lorsque A = BQ, on dit que A est multiple de B ou que B divise A.

• Quel que soit α ∈ K, α ≠ 0 :  B divise A  ⇔  B divise  αA  ⇔  αB divise A.

Dans cette première partie, on s'intéresse à la division, dite euclidienne, d'un polynôme A par un polynôme B comme défini ci-après, également qualifiée de division suivant les puissances décroissantes. L'algorithme est comparable à la division euclidienne dans N.

Théorème et définitions :    

Si A n'est pas multiple de B, la classe d'équivalence (ou de congruence) de A modulo B contient un unique polynôme R de degré strictement inférieur à B appelé reste de la division euclidienne de A par B; l'unique polynôme Q correspondant à R est le quotient de A par B. On a alors :

 A = BQ + R,  d°R < d°B

Unicité :     

Soit d le degré de B. Supposons qu'une classe contienne deux polynômes distincts R et S chacun de degré inférieur à d. On aura S - R = BQ. Si Q = 0, alors R = S. Si Q est non nul, S = R + BQ, donc d° S ≥ d°BQ ≥ d : contraire à l'hypothèse. Donc R est unique.

Existence :     

Si d°A < d, on pose R = A et c'est terminé !
Supposons A = a_nxⁿ + ..., de degré n et B = b_dx^d + ..., de degré d, n ≥ d.
On pose Q₁ = x^n-d × a_n/b_d et A - BQ₁ = R₁.

On a d°R₁ < d°A.
Si d°R₁ < d, c'est gagné : on prend R = R₁.
Sinon on applique le procédé à R₁, on obtient R₂ = R₁ - BQ₂ avec d°R₂ < d°R₁.

Si d°R₂ < d, c'est gagné, on prend R = R₂.
Sinon, on poursuit le procédé, on obtiendrait un R₃ avec d°R₃ < d°R₂, etc.

On obtient ainsi un algorithme semblable à celui de la division euclidienne dans N qui, au bout de n - d + 1 applications au plus du procédé conduit à un R_k de degré nul puisque R_k < d°R_k-1.

 ➔  Il se peut que l'un des R_k soit nul. Dans ce cas l'algorithme s'arrête. On aura R_k-1 - BQ_k = R_k = 0, soit R_k-1 = BQ_k, puis R_k-2 - BQ_k-1 = R_k-1. Par conséquent R_k-2 = B(Q_k-1 + Q_k) : donc R_k-2 est multiple de B et finalement par récurrence finie A = BQ₁, donc A multiple de B.

Les écritures successives précédentes des R_k montrent qu'au bout d'un nombre fini m d'applications du procédé, on a  :

A = B(Q₁ + Q₂ + ... + Q_m) + R_m

Q = Q₁ + Q₂ + ... + Q_m est le quotient de la division euclidienne de A par B, R_m en est le reste.

Exemple : Soit à diviser A = x³ + 2x² - x - 2 par B = x² + 1. On pose l'opération comme pour une division d'entiers :

Programmation :    

• Le programme ci-après effectue la division euclidienne de deux polynômes A et B conformément à l'algorithme étudié ci-dessus. Le lecteur intéressé par la programmation pourra en consulter le listing faisant usage des listes au sens de n-uplets (données ordonnées de n éléments) : on entre les données polynomiales A et B sous forme de listes de leurs coefficients ordonnés suivant les puissances décroissantes. Le programme accepte les écritures fractionnaires et, en sortie, cherche à exprimer les coefficients du quotient et du reste sous forme fractionnaire en utilisant le sous-programme de développement en fraction continue étudié sur cette page.

• Par exemple 4,0,2,0,1/2,-1 signifiera 4x⁵ + 2x³ + x/2 -1. Le polynôme x³ - 9x sera représenté par 1,0,-9,0 et non pas par 1,0,-9 qui correspondrait à x² - 9.

• Par défaut, le programme traite le cas x⁵ - 1 (entrée A : 1,0,0,0,0,-1) divisé par 2x + 1 (entrée B : 2,1). Affichage en sortie :

C'est dire que :

x⁵ - 1 = (2x + 1)(x⁴/2 - x³/4 + x²/8 - x/16 + 1/32) - 33/32

Cette division polynomiale euclidienne permet de parler, tout comme en arithmétique élémentaire, de plus grand diviseur commun à deux polynômes :

Étant donnés deux polynômes A et B dans K[x], l'ensemble de leurs diviseurs communs n'est pas vide : tout polynôme constant (polynôme de degré 0) les divise. Considérons alors l'ensemble J des combinaisons AU + BV où U et V décrivent K[x]. J est un idéal de K[x]; en cet qualité, J est principal. Il existe donc un polynôme D divisant tout élément de J tel que :

1. D divise A (choisir U = 1 et V = 0) et B (choisir U = 0 et V = 1) ;

2. D est défini à une constante multiplicative près;

3. Il existe U_o et V_o tels que D = AU_o + BV_o;

4. Tout polynôme de K[x] divisant A et B divise également D.

Les propriétés 1 et 4 conduisent à qualifier D de plus grand diviseur commun à A et B  au sens d'un diviseur commun de plus haut degré défini à une constante multiplicative près. On note D = pgdc(A,B) ou D = pgcd(A,B). Si D (non nul) est de degré 0, on dit que A et B sont premiers entre eux. Autrement dit :

A et B sont dits premiers entre eux lorsque 1 est un PGCD de A et B

Vocabulaire :    

 ➔  On parle le plus souvent de PGCD (Plus Grand Commun Diviseur) au lieu de PGDC (Plus Grand Diviseur Commun). Il s'agit là de l'influence allemande et anglo-saxonne : dans la langue de Gauss, on parle de Größter Gemeinsamer Teiler (GGT) soit, en anglais Greatest Common Divisor (GCD). Idem pour le Plus Petit Multiple Commun (PPMC ou PPCM) : en allemand Kleineres Gemeinsames Vielfaches (KGV), en anglais : Least Common Multiple (LCM).

Comment calculer du PGCD de deux polynômes A et B :    

On procède aux divisions euclidiennes successives de A par B fournissant un reste R₁, puis de B par R₁ fournissant un reste R₂, etc. :

• A = BQ₁ + R₁, d°R₁ < d°B     • B = R₁Q₂ + R₂, d°R₂ < d°R₁     • R₁ = R₂Q₃ + R₃, d°R₃ < d°R₂
• ...    •  R_k-3 = R_k-2Q_k-1 + R_k-1, d°R_k-1 < d°R_k-2    •  R_k-2 = R_k-1Q_k + R_k, d°R_k < d°R_k-1

Les degrés des restes successifs diminuant strictement, à l'issue d'un nombre fini k de divisions, R_k sera de degré nul, c'est à dire constant, éventuellement nul.

• Si D est un diviseur commun à A et B, alors D divise R₁ et divisant R₁ et B, il divise R₂; et ainsi de suite. Donc D divise R_k.

Inversement deux cas se présentent :

• Si R_k ≠ 0 et D divise R_k alors D est lui-même constant, il divise donc A et B et R_k s'avère être le plus grand diviseur commun à A et B. A et B sont premiers entre eux.

• Si R_k = 0, alors R_k-1 est au moins de degré 1 et si D divise R_k-1 alors il divise R_k-2 et ce faisant il divise R_k-3; et ainsi de suite. Donc D divise A et B. C'est dire que R_k-1 s'avère être le plus grand diviseur commun à A et B.

En conclusion, on retrouve le résultat analogue à l'arithmétique élémentaire :

Le PGCD de deux polynômes A et B est le dernier reste non nul dans la division euclidienne de A par B

• Utiliser le programme JavaScript afin de vérifier que le PGCD de A(x) = 2x³ - 11x² +12x + 9 et de son polynôme dérivé est x - 3 (à une constante multiplicative près). En déduite que A admet x = 3 comme racine double.
• Soit  P un polynôme et P' son polynôme dérivé, justifier que PGCD(P,P') = 1 signifie que P ne possède pas de racine multiple.

 ➔  Tout comme dans l'anneau (Z,+,×) des entiers relatifs, on a le résultat suivant :

Théorème de Bézout :    

Soit D le PGCD de deux polynômes A et B; il existe un unique couple de polynômes U et V tels que AU + BV = D.
Lorsque A et B sont premiers entre eux, leur PGCD est de degré 0; on peut le ramener à 1 et écrire AU + BV = 1.

Programmation :     

L'algorithme est conforme à l'analyse ci-dessus :

• On entre les données polynomiales A et B : a = new Array(), b = new Array; co_b = new Array() sera la copie de b;
• On met à 1 un drapeau d qui évaluera le degré du reste r de la division de A par B;
• Tant que d > 0
    On effectue la division euclidienne de a par b de reste r de degré d : function reste(a,b)
    On copie b dans co_b; a devient b; b devient r;
• Fin tant que.
• Si r ≠ 0, alors les polynômes A et B sont premiers entre eux   // à ce stade r = 0 ou bien r =cte ≠ 0
  Si r = 0 alors le pgcd est le reste précédent, c'est à dire co_b, la copie de b.

Le lecteur intéressé par la programmation pourra en consulter le listing faisant usage des listes au sens de n-uplets (données ordonnées de n éléments) : on entre les données polynomiales A et B sous forme de listes de leurs coefficients ordonnés suivant les puissances décroissantes. Le programme accepte les écritures fractionnaires et, en sortie, cherche à exprimer les coefficients du PGCD sous forme fractionnaire en utilisant le sous-programme de développement en fraction continue étudié sur cette page.

• Par défaut, le programme traite le cas x³ - 9x (entrée A : 1,0,-9,0), 2x² - 5x - 3 (entrée B : 2,-5,-3). Affichage en sortie :

En effet : x³ - 9x = x(x + 3)(x - 3) et 2x² - 5x - 3 = (2x + 1)(x - 3); le PGCD est donc x - 3, soit (en liste) 1,-3.

 i  Le degré de A peut être inférieur à celui de B : dans ce cas, la première division de A par B fournira un quotient nul et le reste sera A, au tour suivant l'algorithme divisera B par A.

 ➔  À la main, on a :

R2 est nul, donc le pgcd est le reste précédent R1 = -5x/4 + 15/4 = -5/4 × (x - 3)
soit x - 3 à une constante multiplicative près.

Division dans un anneau commutatif unitaire, idéal d'anneau, cas des polynômes : »

Si nous ordonnons A et B suivant les puissances croissantes de la variable x (réelle ou complexe), on obtient un autre moyen de division fort utile dans la recherche de valeurs approchées de fonctions rationnelles et de développements limités asymptotiques d'une fonction (au voisinage d'un point où cette fonction n'est pas définie) comme, par exemple le développement limité de f(x) = 1/sin(x) au voisinage de 0.

Théorème :    

Soit A et B deux polynômes, B ne s'annulant pas en 0 (B possède un terme constant : sa valuation est nulle). Alors pour tout entier p, il existe un unique polynôme Q et un unique polynôme R, multiple de x^p, tels que :

A = BQ + R    avec d°Q ≤ p

 R est le reste de la division de la division de A par B suivant les puissances croissantes et Q en est le quotient.

 ➔  Selon cette définition, on a degré Q < p + 1 ≤ v(R), valuation de R. Si A est divisible par B, R sera nul, sinon, la division peut se poursuivre indéfiniment.

Schéma de la démonstration :    

Écrivons A = a_o + a₁x + a₂x² + ... et B = b_o + b₁x + b₂x² + ... avec b_o non nul. A et B sont donc ordonnés suivant les puissances croissantes de x. Si A contient x^p en facteur, le résultat est trivial. Supposons qu'il n'en soit pas ainsi.

• Soit q_o le quotient de a_o par b_o; le polynôme A - q_oB = R_o ne contient pas de terme constant.

• Si d°R_o ≥ p alors Q = q_o et le reste est R_o = r₁x + r₂x² + ... avec r₁ = (a1 - a_o/b_o × b₁).
  Sinon, on réitère le procédé :

• A ← R_o : A devient R_o = r₁x + r₂x² + ... , on divise r₁x par b_o, on obtient un résultat de la forme R_o - q₁B = R₁ avec q₁ = r₁x/b_o et on peut écrire A = B(q_o + q₁) + R₁ avec d°R₁ > d°R_o (car dans R_o - q₁B le monôme de plus faible degré disparaît) à moins que R₁ soit nul et le processus s'arrête.

• A ← R₁ : A devient R₁, et ainsi de suite.

 ➔  On continue ainsi jusqu'à obtenir un R_k nul ou de degré au moins égal à p. On obtient alors une écriture du type :

A - B(q_o + q₁ + ... + q_k) + R_k

R_k est multiple de x^p, le quotient cherché est q_o + q₁ + ... + q_k. On peut prouver (par l'absurde) son unicité.

Dans la pratique, la technique de  division de A par B suivant les puissances croissantes s'effectue de façon semblable à celle suivant les puissances décroissantes.

Remarques :   

1. On peut toujours supposer b_o = 1 en divisant tous les coefficients de B par b_o, quitte à diviser le résultat de la division par b_o.

2. Si b_o est nul : soit b_k le premier coefficient non nul (par rang croissant) de B; on effectue la division de A par B/b_kx^k et on divise le résultat de la division par b_kx^k.

Exemple d'application :    

On sait développer sin x en série entière : sinx = x - x³/3! + x⁵/5! - x⁷/7!... On veut obtenir le développement de 1/sin(x). Le développement de sinx ne possède pas de terme constant. Selon la remarque 2 ci-dessus, on divise 1 (polynôme A) par B = sin (x)/x et on divisera par x le résultat.

à la "main" :

Résultat que le programme exprime par (les 0 isolés signifiant l'absence de la puissance correspondante) :

Divisons maintenant par x :

1/sin(x) = 1/x + x/6 + 7x³/360 + 31x⁵/15120 + o(x⁵)

Programmation :    

Le programme ci-après effectue la division suivant les puissances croissantes de deux polynômes A et B conformément à l'algorithme étudié ci-dessus. Le lecteur intéressé par la programmation pourra en consulter le listing faisant usage des listes au sens de n-uplets (données ordonnées de n éléments) : on entre les données polynomiales A et B sous forme de listes de leurs coefficients ordonnés suivant les puissances croissantes. Le programme accepte les écritures fractionnaires et, en sortie, cherche à exprimer les coefficients du quotient et du reste sous forme fractionnaire en utilisant le sous-programme de développement en fraction continue étudié sur cette page.

• Par exemple 1,1/2,0,-1/6,0,4 signifie 1 + x/2 - x³/6 + 4x⁵. Le polynôme x³ - 9x = -9x + x³ sera représenté par  0,-9,0,1.

Rappel : B ne doit pas s'annuler en 0 : terme constant non nul. Si ce n'est pas le cas, on divise B par x^v où v est le terme de plus bas degré (valuation de B) et on  divisera ensuite le résultat par ce même x^v.

• La nouvelle version du programme affiche le reste R de la division (qui est un multiple de x^p). Mais on peut aussi le calculer à la main en tant que A - B × Q.

 ➔  Par défaut, le programme ci-dessous effectue la division de x⁵ - 1 par 2x + 1 suivant les puissances croissantes à l'ordre p = 5. On entre donc -1,0,0,0,0,1 (équivalent à -1 + x⁵), puis 1,2 (équivalent à 1 + 2x) et le degré p = 5. Ce qui conduit à :

C'est dire que :

- 1 + x⁵ = (1 + 2x)(-1 + 2x - 4x² + 8x³ - 16x⁴ + 33x⁵) - 66x^{6
(on notera que ce résultat a peu de rapport avec la division euclidienne de ces mêmes polynômes)}

 i  Remarque :       

Pour diviser -1 + x⁵ par x² + 2x³ on procéderait à la même division en divisant ensuite le quotient par x², le reste est inchangé :

- 1 + x⁵ = (x²  + 2x³)(-1/x² + 2/x - 4x + 8x - 16x² + 33x³) - 66x⁶

• Ci-dessous, on  a effectué  la division de 1 par  1 - x²/6 + x⁴/120 suivant les puissances croissantes avec p = 4. Ce qui conduit à :

On doit comprendre :

A =             B             ×              Q                 +              R
1 = (1 - x²/6 + x⁴/120) × (1 + x²/6 + 7 x⁴/360) + (x⁶/540 - 7x⁸/43200)

à l'ordre 5, le quotient est inchangé car il ne contient (comme le reste) dans ce cas particulier que des puissances paires : le coefficient de x⁵ est nul :

Un autre exemple d'application du programme :   

Nous allons calculer le développement de tan(x) à l'ordre 7 obtenu en divisant suivant les puissances croissantes le développement en série de sin(x) par celui de cos(x) en se limitant à l'ordre 7 :

• sin(x) = x - x³/3! + x⁵/5! - x⁷/7! + ... = 0 + x + 0 - x³/6 + 0 + x⁵/120 + 0 - x⁷/5040 + ...

• cos(x) =1 - x²/2! + x⁴/4! - x⁶/6! + ... = 1 + 0 - x²/2 + 0 + x⁴/24 + 0 - x⁶/720 + 0 + ...

Le programme comprend les entrées fractionnaires et, en sortie, cherche à exprimer les coefficients du quotient et du reste sous forme fractionnaire en utilisant le sous-programme de développement en fraction continue étudié sur cette page. On entre les coefficients sous forme de listes et suivant les puissances croissantes :

• A = sin(x) : 0,1,0,-1/6,0,1/120,0,-1/5040 (le 1er zéro correspond à l'absence de terme constant);

• B = cos(x) : 1,0,-1/2,0,1/24,0,-1/720,0

• degré désiré p = 7.

On obtient (le 1er 0 indique qu'il n'y a pas de terme constant) :

C'est dire que :

tan(x) = x + x³/3 +2x⁵/15 + 17x⁷/315 + o(x⁷)

 i  Le calcul du reste laisse présager un terme de degré 9 égal à 331x⁹/15120. Mais les développements fournis étant d'ordre 7, il n'y a pas de certitude... Il serait vain de demander à développer au-delà d'un rang non fourni en entrée.