Le PGCD de deux nombres de Mersenne

La stratégie : faire marcher l'algorithme d'Euclide sur les exposants. Une division euclidienne entre exposants se relève en une division euclidienne entre les nombres $2^n-1$ ; on démontre cette correspondance, puis on suit les deux algorithmes en parallèle, par une récurrence forte. Ce qu'on a le droit d'utiliser : le théorème de la division euclidienne (existence et unicité du quotient et du reste), le lemme d'Euclide — si $x=yq+r$, alors $x\wedge y=y\wedge r$ —, la valeur $x\wedge 0=x$ pour $x\ge 1$, et la somme géométrique. Tout se passe entre entiers naturels : c'est le cadre du programme de PTSI, qui fait l'arithmétique dans $\mathbb{N}$, et l'on n'aura besoin d'aucun entier négatif.

Notation. Pour $n\in \mathbb{N}$, posons $M_n=2^n-1$. On a $M_0=0$, $M_n\ge 1$ dès que $n\ge 1$, et la suite $(M_n)$ est strictement croissante, puisque $2^{n+1}-1>2^n-1$. (Pour $n$ premier, les $M_n$ sont les nombres de Mersenne.) L'énoncé s'écrit $M_a\wedge M_b=M_{a\wedge b}$.

1) Le reste de $M_a$ dans la division par $M_b$. Soient $a,b\ge 1$, et soit $a=bq+r$ la division euclidienne de $a$ par $b$, avec $0\le r<b$. Alors $$2^a-1=2^r\cdot 2^{bq}-1=2^r\left(2^{bq}-1\right)+\left(2^r-1\right).$$ Or, par la somme géométrique de raison $2^b\ne 1$, $$2^{bq}-1={\left(2^b\right)}^q-1=\left(2^b-1\right)\left(1+2^b+2^{2b}+\cdots +2^{(q-1)b}\right),$$ ce qui reste vrai pour $q=0$, les deux membres étant alors nuls (la somme est vide). Donc $$M_a=M_b\cdot Q+M_r,$$ avec $Q=2^r\left(1+2^b+\cdots +2^{(q-1)b}\right)\in \mathbb{N}$.

Le point délicat : c'est bien la division euclidienne. Écrire $M_a=M_{b}Q+M_r$ ne suffit pas : il faut la condition sur le reste, sans laquelle l'unicité ne s'applique pas. Or $0\le r<b$ entraîne $0\le M_r<M_b$, la suite $(M_n)$ étant strictement croissante. Par unicité dans le théorème de la division euclidienne, le reste de la division de $M_a$ par $M_b$ est exactement $M_r$ : les deux divisions « marchent au pas ».

2) Le lemme d'Euclide. Appliqué à l'égalité $M_a=M_{b}Q+M_r$, il donne $$M_a\wedge M_b=M_b\wedge M_r.$$ Et, du côté des exposants, appliqué à $a=bq+r$ : $a\wedge b=b\wedge r$. Les deux algorithmes remplacent le couple $(a,b)$ par $(b,r)$, et le couple $(M_a,M_b)$ par $(M_b,M_r)$ : ils avancent ensemble.

3) La conclusion, par récurrence forte sur $b$. Pour $b\ge 1$, notons $\mathcal{H}(b)$ l'assertion « pour tout $a\in {\mathbb{N}}^{\ast }$, $M_a\wedge M_b=M_{a\wedge b}$ ». Soit $b\ge 1$ tel que $\mathcal{H}(r)$ soit vraie pour tout $r\in \{1,\dots ,b-1\}$ (hypothèse vide si $b=1$), et soit $a\in {\mathbb{N}}^{\ast }$, avec $a=bq+r$, $0\le r<b$.

Si $r=0$, alors $b$ divise $a$, donc $a\wedge b=b$ ; et $M_r=M_0=0$, donc $M_a\wedge M_b=M_b\wedge 0=M_b=M_{a\wedge b}$.

Si $r\ge 1$, alors $1\le r\le b-1$, et l'hypothèse $\mathcal{H}(r)$, appliquée à l'entier $b$, donne $M_b\wedge M_r=M_{b\wedge r}$. Avec le 2) : $$M_a\wedge M_b=M_b\wedge M_r=M_{b\wedge r}=M_{a\wedge b}.$$

Dans les deux cas $\mathcal{H}(b)$ est vraie ; par récurrence forte, elle l'est pour tout $b\ge 1$, ce qui est l'énoncé. (Pour $b=1$, seul le cas $r=0$ se présente : c'est l'initialisation, contenue dans le raisonnement.)

Contrôle numérique. Pour $a=12$ et $b=8$ : $2^{12}-1=4095$ et $2^8-1=255$. L'algorithme d'Euclide donne $4095=16\times 255+15$, puis $255=17\times 15+0$ : le PGCD vaut $15=2^4-1$, et $12\wedge 8=4$. On observe la correspondance du 1) : le premier reste, $15$, est $2^4-1$, où $4$ est le reste de $12$ par $8$. Une vérification exhaustive pour tous les exposants jusqu'à $40$ ne trouve aucune exception.

Un corollaire. $M_a$ divise $M_b$ si et seulement si $M_{a\wedge b}=M_a$, c'est-à-dire, $(M_n)$ étant strictement croissante, $a\wedge b=a$ : $2^a-1$ divise $2^b-1$ si et seulement si $a$ divise $b$. Si $n=de$ avec $1<d<n$, $M_d$ est donc un diviseur de $M_n$ strictement compris entre $1$ et $M_n$ : un nombre $2^n-1$ premier a un exposant $n$ premier.

Ce que l'exercice installe. La division euclidienne se transporte d'un ensemble de nombres à un autre : $n\mapsto 2^n-1$ change l'arithmétique des exposants en arithmétique des nombres. Le transport se refera au chapitre des polynômes, où la division de $X^a-1$ par $X^b-1$ a pour reste $X^r-1$, par le même calcul. Et l'on retiendra le geste de rigueur : $x=yQ+R$ n'est une division euclidienne que si $0\le R<y$.