# Polynôme/Arithmétique des polynômes

$K$ désigne toujours un corps commutatif et $K[X]$ l'anneau des polynômes à coefficients dans ce corps.

## Division euclidienne et divisibilité dans K[X]

Il existe une unique division euclidienne dans $K[X]$, c'est-à-dire :
    $\forall A,B\in K[X]\times (K[X]\setminus \{0\})\quad \exists !(Q,R)\in (K[X])^{2}\quad A=BQ+R\mathrm {\;et\;} \deg R<\deg B$.
$Q$ est appelée quotient de $A$ par $B$ et $R$ reste.
La démonstration est généralement faite en deux temps. L'unicité est plutôt plus facile. Avec les notations du théorème :
* Le couple (Q, R), s'il existe, est unique :
La démonstration se fonde sur une propriété du degré d'un polynôme ; le degré du produit de deux polynômes M et N est égal à la somme des degrés de chaque polynôme :
${\text{deg }}(MN)={\text{deg }}M+{\text{deg }}N$
On suppose l'existence de deux couples (Q$_1$, R$_1$), (Q$_2$, R$_2$) résultats de la division euclidienne de A par B, on va montrer qu'ils sont égaux. On dispose des égalités :
$A=BQ_{1}+R_{1},\quad A=BQ_{2}+R_{2}\quad {\text{donc}}\quad (1)\quad B(Q_{1}-Q_{2})=R_{2}-R_{1}.$
Le polynôme B(Q$_1$ – Q$_2$) est donc de degré strictement inférieur à celui de B, ce qui n'est possible que si Q$_1$ – Q$_2$ est nul. L'égalité (1) montre alors que R$_1$ – R$_2$ est aussi nul.
* Il existe un couple (Q, R) satisfaisant l'identité de la division euclidienne :
Soient m et n les degrés de A et B. Si m < n (y compris si m = –∞, c'est-à-dire si A = 0), il suffit de prendre Q égal au polynôme constant 0 et R égal à A pour établir l'existence. Raisonnons par récurrence pour établir les autres cas. Soit p ≥ n ; supposons la propriété démontrée pour toute valeur de m strictement inférieure à p et montrons-la pour m = p. Pour cela, notons
$A=a_{m}X^{m}+a_{m-1}X^{m-1}+\cdots +a_{0}\quad {\text{et}}\quad B=b_{n}X^{n}+b_{n-1}X^{n-1}+\cdots +b_{0}\quad {\text{avec}}\quad b_{n}\neq 0$
et posons
$(2)\quad A_{1}=A-{\frac {a_{m}}{b_{n}}}X^{m-n}B.$
Ce polynôme est de degré inférieur à m, strictement (car les monômes de degré m des deux membres de cette différence sont égaux donc s'éliminent). On peut donc lui appliquer l'hypothèse de récurrence : il existe deux polynômes Q$_1$ et R$_1$ tels que :
$(3)\quad A_{1}=Q_{1}B+R_{1}\quad {\text{avec}}\quad \deg R_{1}<\deg B.$
En combinant (2) et (3), on obtient :
$A=\left({\frac {a_{m}}{b_{n}}}X^{m-n}+Q_{1}\right)B+R_{1}\quad {\text{avec}}\quad \deg R_{1}<\deg B,$
ce qui établit la proposition.
Exemple : Division de x$^4$-x$^3$+x$^2$-x+8 par x$^2$+3x+1
* Étape 1 : division de x$^4$-x$^3$+x$^2$ par x$^2$+3x+1 (quotient x$^2$, reste -4x$^3$)
    x$^4$- x $^3$+ x$^2$- x+ 8x$^2$ + 3x + 1 x$^4$+ 3x$^3$+ x$^2$x$^2$ - 4x$^3$
* Étape 2 : division de -4x$^3$ - x par x$^2$ + 3x + 1 (quotient -4x, reste 12x$^2$ + 3x)
    x$^4$- x $^3$+ x$^2$- x+ 8x$^2$ + 3x + 1 x$^4$-3x$^3$+ x$^2$x$^2$ - 4x - 4x$^3$- x -4x$^3$- 12x$^2$-4x + 12x$^2$+ 3x
* Étape 3 : division de 12x$^2$ - 3x + 8 par x$^2$ + 3x + 1 (quotient 12, reste -33x - 4)
    x$^4$- x $^3$+ x$^2$- x+ 8x$^2$ + 3x + 1 x$^4$+ 3x$^3$+ x$^2$x$^2$ - 4x + 12 - 4x$^3$- x -4x$^3$- 12x$^2$-4x + 12x$^2$+ 3x+ 8 12x$^2$+ 36x+12 - 33x- 4
* Conclusion : x$^4$ - x $^3$ + x$^2$ - x + 8 = (x$^2$ + 3x + 1)(x$^2$ - 4x + 12) - 33x - 4
Soient $A$ et $B$ deux polynômes.
On dit que $B$ divise $A$ (ce qu'on note $B\mid A$) s'il existe $P\in K[X]$ tel que $A=PB$ :
    $B\mid A\iff \exists P\in K[X]\quad A=PB$.
Soient $A,B,C\in K[X]$ et $\lambda \in K^{*}$.
* $A\mid \lambda \iff A{\text{ constant.}}$
* $A\mid B{\text{ et }}B\mid C\Rightarrow A\mid C$ (transitivité).
* $A\mid B{\text{ et }}A\mid C\Rightarrow A\mid BU+CV\quad \forall U,V\in K[X]$.
* $\left(A\mid B{\text{ et }}B\mid A\right)\iff \left(\exists \mu \in K^{*}\quad A=\mu B\right)$.
Les démonstrations se font comme dans $\mathbb {Z}$ (voir le cours d'arithmétique).

## PGCD et PPCM
### Définitions

Soient $A,B\in K[X]$.
* Un PGCD (Plus Grand Diviseur Commun) de $A$ et $B$ est un polynôme $D$ qui divise $A$ et $B$ et tel que tout diviseur commun à $A$ et $B$ divise $D$ (c'est donc le "plus grand" au sens de la relation d'ordre "divise") .
* Un PPCM (Plus Petit Commun Multiple) de $A$ et $B$ est un polynôme $M$ qui est divisible par $A$ et $B$ et tel que tout multiple commun à $A$ et $B$ soit divisible par $M$ (c'est donc le "plus petit" au sens de la relation d'ordre "divise") .
Remarques :
* $P\mid Q\iff \operatorname {pgcd} (P,Q)=P\iff \operatorname {ppcm} (P,Q)=Q$.
* Deux PGCD ou PPCM d'un même couple de polynômes sont associés (c'est-à-dire égaux à une constante multiplicative près).
* Comme dans $\mathbb {Z}$, deux polynômes sont dits premiers entre eux si, et seulement si, leur PGCD vaut 1 (en fait, cela équivaut à dire que leur PGCD est un polynôme constant).

### Algorithme d'Euclide

Il est le même que dans $\mathbb {Z}$. On établit le lemme d'Euclide :
Soient $A,B\in K[X]$. Alors $\forall Q,R\in K[X]$, si $A=BQ+R$ on a :
    $\operatorname {pgcd} (A,B)=\operatorname {pgcd} (B,R)$.
Il faut montrer que l’ensemble ${\mathcal {D}}(A,B)$ des diviseurs communs à $A$ et $B$ est égal à ${\mathcal {D}}(B,R)$.
Soit $C$ un diviseur de $B$. ALors, $C\mid A\Rightarrow C\mid A-BQ=R$ et réciproquement, $C\mid R\Rightarrow C\mid BQ+R=A$.
On a bien l'égalité ${\mathcal {D}}(A;B)={\mathcal {D}}(B;Q)$ : si ces ensembles sont égaux, alors leurs plus grands éléments aussi, d'où le résultat.
On en déduit l'algorithme d'Euclide :
Soient $A,B\in K[X]$ tels que $\deg A>\deg B$.
| Opération | Reste $R$ | Commentaires |
| on divise $A$ par $B$ | $R_{0}$ | $\deg 0\leq \deg R_{0}<\deg B{\mbox{ et }}pgcd(A,B)=pgcd(B,R_{0})$ |
| si $R_{0}\neq 0$, on divise $B$ par $R_{0}$ | $R_{1}$ | $\deg 0\leq \deg R_{1}<\deg R_{0}{\mbox{ et }}pgcd(B,R_{0})=pgcd(R_{0},R_{1})$ |
| si $R_{n}\neq 0$, on divise $R_{n-1}$ par $R_{n}$ | $0$ | $pgcd(R_{n-1},R_{n})=R_{n}$ |

## Théorèmes d'arithmétique

Ces théorèmes se démontrent comme dans $\mathbb {Z}$.
* $\forall A,B\in K[X]\quad \exists U,V\in K[X]\quad AU+BV=\operatorname {pgcd} (A,B)$.
* $\operatorname {pgcd} (A;B)=1\iff \left(\exists U,V\in K[X]\quad AU+BV=1\right)$.
Soient $A,B,C\in K[X]$.
Si $A\mid BC$ et $\operatorname {pgcd} (A,B)=1$, alors $A\mid C$.

## Idéaux de K[X]

K[X] est un anneau principal, ce qui signifie que tout idéal de K[X] est principal : plus précisément, si $I$ est un idéal de K[X], alors :
    $\exists P\in K[X]\quad I=(P)=\{PQ\mid Q\in K[X]\}$.
L'idéal $\{0\}$ est engendré par le polynôme nul.
Soit maintenant $I$ un idéal non nul de $K[X]$. Soit, parmi les éléments non nuls de $I$, un polynôme $B$ de degré minimum.
Comme $B\in I$, par définition d'un idéal, $(B)\subset I$.
Réciproquement, soit $A\in I$. Par division euclidienne de $A$ par $B$, il existe $Q,R\in K[X]$ tels que $A=BQ+R$ et $\deg(R)<\deg(B)$.
Le polynôme $R=A-BQ$ appartient à $I$, comme somme de deux éléments de ce même idéal. Par choix de $B$, la condition $\deg(R)<\deg(B)$ implique $R=0$ donc $A=BQ\in (B)$.
Ceci prouve que $I\subset (B)$ donc finalement, $I=(B)$.

## Polynômes premiers et irréductibles

Soit $P\in K[X]$ non constant.
* Le polynôme $P$ est dit irréductible si ses seuls diviseurs sont les polynômes constants et ceux de la forme $\lambda P\;(\mathrm {avec\;} \lambda \in K)$.
* Le polynôme $P$ est dit premier si :
    $\forall A,B\in K[X]\quad P\mid AB\Rightarrow \left(P\mid A{\text{ ou }}P\mid B\right)$.
Comme dans tout anneau vérifiant le théorème de Gauss, on a :
Un polynôme est premier si (et seulement si) il est irréductible.
Mieux : on a vu que $K[X]$ est principal ; on en déduit :
L'anneau $K[X]$ est factoriel ; cela signifie que tout polynôme non constant admet une décomposition en produit de facteurs irréductibles, unique à l’ordre des facteurs près et à association près.
| Définitions | Dérivation formelle |