Introduction : Le Concept Fondateur
La division euclidienne est sans doute l’algorithme le plus fondamental de l’arithmétique. Enseignée dès l’école primaire pour les nombres entiers, elle formalise l’idée intuitive de « partager en parts égales » tout en laissant un reste « plus petit » que la taille des parts.
Ce qui est remarquable, c’est que ce même principe peut être étendu à d’autres structures algébriques, notamment l’anneau des polynômes à coefficients dans un corps. Dans les deux cas, l’existence d’une telle division est la clé de voûte de toute la théorie arithmétique de l’anneau : elle garantit que l’anneau est euclidien, et donc principal et factoriel. C’est grâce à elle que l’on peut définir un PGCD, utiliser l’algorithme d’Euclide et prouver des résultats aussi puissants que l’identité de Bézout ou le lemme de Gauss.
La Division Euclidienne dans l’Anneau des Entiers $\mathbb{Z}$
C’est le cadre le plus familier. La division euclidienne dans $\mathbb{Z}$ consiste à diviser un entier (le dividende) par un autre entier non nul (le diviseur) pour obtenir un quotient et un reste.
Soit $a \in \mathbb{Z}$ (le dividende) et $b \in \mathbb{Z} \setminus \{0\}$ (le diviseur).
Il existe un unique couple d’entiers $(q, r) \in \mathbb{Z}^2$ tel que :
$$ a = bq + r \quad \text{avec} \quad 0 \le r < |b| $$
L'entier $q$ est le quotient et l'entier $r$ est le reste.
Points importants :
- L’unicité du couple (quotient, reste) est garantie.
- La condition sur le reste $0 \le r < |b|$ est cruciale. Elle assure que le reste est toujours positif et strictement plus petit que la valeur absolue du diviseur, ce qui garantit la terminaison de l'algorithme d'Euclide.
Exemple
Soit $a = -50$ et $b = 6$. On cherche $(q,r)$ tels que $-50 = 6q + r$ avec $0 \le r < 6$.
Une division simple donne $-50/6 \approx -8.33$. On ne peut pas prendre $q=-8$ car cela donnerait $-50 = 6(-8) – 2$, et le reste $-2$ n’est pas positif.
Il faut choisir le quotient entier immédiatement inférieur ou égal à $-8.33$, c’est-à-dire $q=-9$.
$$ -50 = 6 \cdot (-9) + r $$
$$ -50 = -54 + r \implies r = 4 $$
Le couple unique est $(q, r) = (-9, 4)$. On a bien $0 \le 4 < 6$.
La Division Euclidienne dans l’Anneau des Polynômes $K[X]$
Le processus se généralise de manière très naturelle aux polynômes à une indéterminée sur un corps $K$. La « taille » des polynômes n’est plus mesurée par la valeur absolue, mais par leur degré.
Soit $K$ un corps. Soient $A(X) \in K[X]$ (le dividende) et $B(X) \in K[X] \setminus \{0\}$ (le diviseur).
Il existe un unique couple de polynômes $(Q(X), R(X)) \in K[X]^2$ tel que :
$$ A(X) = B(X)Q(X) + R(X) \quad \text{avec} \quad R(X)=0 \text{ ou } \deg(R) < \deg(B) $$
Le polynôme $Q(X)$ est le quotient et $R(X)$ est le reste.
L’algorithme pour trouver $Q$ et $R$ est la division longue (ou « potence »), qui est une procédure systématique.
Exemple dans $\mathbb{R}[X]$
Divisons $A(X) = 2X^4 – X^3 + X – 1$ par $B(X) = X^2 + X + 1$.
On procède par étapes en annulant le terme de plus haut degré de $A$ à chaque fois :
- Pour annuler $2X^4$, on multiplie $B(X)$ par $2X^2$.
$A – 2X^2 B = (2X^4 – X^3 + X – 1) – (2X^4 + 2X^3 + 2X^2) = -3X^3 – 2X^2 + X – 1$. - Pour annuler $-3X^3$, on multiplie $B(X)$ par $-3X$.
$(-3X^3 – 2X^2 + X – 1) – (-3X^3 – 3X^2 – 3X) = X^2 + 4X – 1$. - Pour annuler $X^2$, on multiplie $B(X)$ par $1$.
$(X^2 + 4X – 1) – (X^2 + X + 1) = 3X – 2$.
Le processus s’arrête car le degré de $3X-2$ (qui est 1) est strictement inférieur au degré de $B(X)$ (qui est 2).
Le quotient est la somme des termes que nous avons utilisés : $Q(X) = 2X^2 – 3X + 1$.
Le reste final est $R(X) = 3X – 2$.
On a donc l’identité :
$$ 2X^4 – X^3 + X – 1 = (X^2 + X + 1)(2X^2 – 3X + 1) + (3X – 2) $$