cours/algorithme d'euclide pour les polynômes.md

aliases, up, tags

aliases	up	tags
	algorithme d'euclide PGCD de polynômes	s/maths/algèbre

Soit K un corps Soient P, Q \in K[X] avec Q \neq 0

Posons : \begin{cases} P_0 = P\\ Q_0= Q\\ \forall k \geq 0,\quad \begin{cases} P_{k+1} = Q_{k}\\ Q_{k+1} = \text{reste de la division de } P_{k} \text{ par } Q_{k} \end{cases} \end{cases}

[!proposition]+ Soit k_0 = \min \{ k\in \mathbb{N} \mid Q_{k+1} = 0 \} Alors k_0 est bien défini et : \operatorname{PGCD}(P, Q) = a Q_{k_0} où a \in K^{*} est tel que aQ_{k_0} est polynôme unitaire

[!démonstration]- Démonstration \forall k \geq 0, Q_{k+1} est le reste de la division euclidienne de polynômes de P_{k} par Q_{k} Donc \operatorname{deg}Q_{k+1} < \operatorname{deg}Q_{k} Ainsi, (Q_{k})_{k \in \mathbb{N}} est strictement décroissante et donc \exists k_0,\quad Q_{k_0+1} = 0

---

Montrons par récurrence sur k \in \mathbb{N} que : (H_{k}) : \forall D \in K[X],\quad \begin{cases} D \mid P\\ D\mid Q \end{cases} \iff \begin{cases} D \mid P_{k} \\ D \mid Q_{k} \end{cases}

• H_0 est évident puisque P_0 = P et Q_0 = Q

• supposons H_{k} vraie pour k \geq 0, et montrons que H_{k+1} est vraie aussi On a \exists A \in K[X],\quad P_{k} = A \underbracket{Q_{k}}_{=P_{k+1}} + Q_{k+1} Soit D \in K[X] Par hypothèse de récurrence on a : \begin{cases} D\mid P\\ D \mid Q \end{cases} \iff \begin{cases} D \mid P_{k} \\ D \mid Q_{k} \end{cases} Or, Q_{k} = P_{k+1} donc on a : \begin{cases} D \mid P \\ D \mid Q \end{cases} \iff \begin{cases} D \mid Q_{k+1} \\ D \mid P_{k+1} \end{cases}

  Soit k_0 tel que \begin{cases} Q_{k_0} \neq 0 \\ Q_{k_0+1} = 0 \end{cases} Soit R = aQ_{k_0} où a \in K^{*} est choisi pour que R soit polynôme unitaire

  On a R = aQ_{k_0} \mid 0 = Q_{k_0+1} et aussi R \mid P_{k_0+1} = Q_{k_0} Or, par hypothèse de récurrence, on en déduit que \begin{cases} R \mid P \\ R \mid Q \end{cases} et donc R \mid \operatorname{PGCD}(P, Q)

  Réciproquement : \operatorname{PGCD}(P, Q) divise P et Q, donc par hypothèse de récurrence : \operatorname{PGC}(P, Q) divise P_{k_0+1} = Q_{k_0} et comme Q_{k_0} et R sont polynômes associés on a \operatorname{PGCD}(P, Q) \mid R donc R et \operatorname{PGCD}(P, Q) sont polynômes associés et polynôme unitaire, il sont donc égaux : R = \operatorname{PGCD}(P, Q)