---
aliases: 
up:
  - "[[algorithme d'euclide]]"
  - "[[PGCD de polynômes]]"
tags:
  - 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|unitaire]]
> 
> > [!démonstration]- Démonstration
> > $\forall k \geq 0$, $Q_{k+1}$ est le reste de la [[division euclidienne de polynômes|division euclidienne]] 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|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|associés]] on a $\operatorname{PGCD}(P, Q) \mid R$
> >   donc $R$ et $\operatorname{PGCD}(P, Q)$ sont [[polynômes associés|associés]] et [[polynôme unitaire|unitaires]], il sont donc égaux :
> >   $R = \operatorname{PGCD}(P, Q)$
> >   
> >