Montrer que pour m, n ∈ ℕ* : (Xⁿ - 1 ) ∧ (Xᵐ - 1 ) = X^n ∧ m - 1.

La stratégie : par l'algorithme d'Euclide, transporté des polynômes aux exposants. L'algorithme sur $\left(X^n-1,X^m-1\right)$ va reproduire, exposant par exposant, l'algorithme d'Euclide soustractif sur le couple $(n,m)$.

1) L'identité qui fait tout. Supposons $n>m\ge 1$. Alors $$X^n-1=X^{n-m}\left(X^m-1\right)+\left(X^{n-m}-1\right)$$ En effet le membre de droite vaut $X^n-X^{n-m}+X^{n-m}-1=X^n-1$.

⚠️ Ce n'est pas la division euclidienne, et ce n'est pas grave. Si $n-m\ge m$, le « reste » $X^{n-m}-1$ a un degré $\ge m$ : la relation n'est donc pas la division euclidienne de $X^n-1$ par $X^m-1$. Mais on n'en a pas besoin. Ce qu'on utilise est plus faible et toujours vrai : dès qu'on écrit $A=QB+R$, un polynôme divise $A$ et $B$ si et seulement si il divise $B$ et $R$. Les deux couples ont donc les mêmes diviseurs communs, donc le même pgcd : $$\left(X^n-1\right)\wedge \left(X^m-1\right)=\left(X^m-1\right)\wedge \left(X^{n-m}-1\right)$$

2) La descente. Notons $g(n,m)=\left(X^n-1\right)\wedge \left(X^m-1\right)$. On vient d'établir $$g(n,m)=g(n-m,m)(n>m),g(n,m)=g(m,n),g(n,n)=X^n-1$$ Ce sont exactement les trois règles de l'algorithme d'Euclide soustractif calculant $n\wedge m$. Une récurrence forte sur $n+m$ conclut : à chaque étape le couple d'exposants se transforme comme dans l'algorithme numérique, qui aboutit en un nombre fini d'étapes au couple $(d,d)$ avec $d=n\wedge m$, où la valeur est $X^d-1$. Donc $$\left(X^n-1\right)\wedge \left(X^m-1\right)=X^{n\wedge m}-1$$ (le pgcd est bien unitaire, comme le veut la convention).

3) Lecture par les racines (seconde preuve, sur $\mathbb{C}$). Les racines de $X^n-1$ sont les racines $n$-ièmes de l'unité, toutes simples ; celles communes aux deux polynômes sont les $\omega$ tels que ${\omega }^n={\omega }^m=1$, c'est-à-dire les racines $d$-ièmes de l'unité avec $d=n\wedge m$ (car $\{k:{\omega }^k=1\}$ est le sous-groupe de $\mathbb{Z}$ engendré par l'ordre de $\omega$). Le pgcd, produit des facteurs $X-\omega$ communs, est donc $X^d-1$.

Contrôle numérique ($\mathrm{pgcd}$ calculé par l'algorithme d'Euclide sur les polynômes) :

$(n,m)$	$n\wedge m$	$\left(X^n-1\right)\wedge \left(X^m-1\right)$
$(7,3)$	$1$	$X-1$
$(4,6)$	$2$	$X^2-1$
$(12,8)$	$4$	$X^4-1$
$(6,6)$	$6$	$X^6-1$

(Les $144$ couples $(n,m)$ avec $1\le n,m\le 12$ ont été vérifiés : aucun écart.)

Ce que l'exercice installe. Le même énoncé vaut pour les entiers : $\left(2^n-1\right)\wedge \left(2^m-1\right)=2^{n\wedge m}-1$, et la preuve est mot pour mot la même. C'est le signe que $\mathbb{Z}$ et $\mathbb{K}[X]$ partagent une seule et même arithmétique, celle des anneaux euclidiens.