Quand $x^d-1$ divise $x^n-1$

Ce qu'on montre. Une divisibilité entre polynômes, à partir d'une divisibilité entre entiers. L'outil est l'identité de la somme géométrique, écrite sur les polynômes.

L'identité de base. Pour tout polynôme $Y$ et tout entier $m\ge 1$ : $$Y^m-1=(Y-1)(Y^{m-1}+Y^{m-2}+\cdots +Y+1).$$ Elle se vérifie en développant le membre de droite : le produit vaut ${\sum }_{k=1}^m{Y}^k-{\sum }_{k=0}^{m-1}{Y}^k$, somme télescopique dont il ne reste que $Y^m-1$.

Application. Supposons $d\mid n$ et écrivons $n=dm$ avec $m\in {\mathbb{N}}^{\ast }$. Posons $Y=x^d$, qui est un polynôme. Alors $Y^m=x^{dm}=x^n$, et l'identité donne $$x^n-1=(x^d-1)(x^{d(m-1)}+x^{d(m-2)}+\cdots +x^d+1).$$ Le second facteur est un polynôme à coefficients réels : $x^d-1$ divise donc $x^n-1$, avec un quotient explicite.

Point délicat. La substitution $Y=x^d$ est licite parce que l'identité est valable pour tout polynôme $Y$, et pas seulement pour une variable de degré $1$. C'est ce changement de variable qui fait tout le travail : sans lui, on serait tenté de poser une division euclidienne à $n$ étapes.

Illustration : $d=3$, $n=9$, donc $m=3$. $$x^9-1=(x^3-1)(x^6+x^3+1).$$ Contrôle en $x=2$ : $512-1=511$ d'un côté, $7\times (64+8+1)=7\times 73=511$ de l'autre.