Euclide à l'étage des exposants : $(2^a-1)\wedge (2^b-1)=2^{a\wedge b}-1$

La stratégie. L'algorithme d'Euclide repose sur un seul lemme : si $b=aq+r$, alors $b\wedge a=a\wedge r$. On va montrer qu'une division euclidienne des exposants se traduit par une division euclidienne des nombres de Mersenne — alors l'algorithme sur $(b,a)$ se recopie terme à terme sur $(M_b,M_a)$, et s'arrête au même endroit.

a) La divisibilité se transporte. Si $b=ak$ avec $k\in \mathbb{N}$, alors, avec $x=2^a$ et $d=k$ dans l'identité $x^d-1=(x-1)(x^{d-1}+\cdots +1)$ : $$M_b=2^{ak}-1=\left(2^a-1\right)\left(2^{a(k-1)}+2^{a(k-2)}+\cdots +2^a+1\right),$$ et le second facteur est un entier. Donc $M_a\mid M_b$. (Pour $k=0$, $M_0=0$ est divisible par tout.)

b) Un pas d'Euclide sur les exposants. Soit $b=aq+r$ avec $0\le r<a$. Écrivons $$M_b=2^{aq+r}-1=2^r\cdot 2^{aq}-1=2^r\left(2^{aq}-1\right)+\left(2^r-1\right)=2^r{M}_{aq}+M_r.$$ Par le a), $M_a$ divise $M_{aq}$ : il existe un entier $Q_0$ tel que $M_{aq}=M_a{Q}_0$, et donc $M_b=M_a\cdot (2^r{Q}_0)+M_r$. C'est une égalité de la forme $M_b=M_{a}Q+R$ avec $Q=2^r{Q}_0\in \mathbb{N}$ et $R=M_r$. Pour que ce soit la division euclidienne, il faut l'encadrement du reste : $0\le M_r<M_a$, qui découle de $0\le r<a$ et de la stricte croissance de $k\mapsto 2^k-1$. Le reste de $M_b$ par $M_a$ est $M_r$, où $r$ est le reste de $b$ par $a$.

Le point délicat. Sans l'encadrement $0\le M_r<M_a$, l'égalité ci-dessus serait une simple identité, pas un pas d'Euclide, et le lemme du PGCD ne s'appliquerait pas.

c) La descente. Par le lemme d'Euclide, $M_b\wedge M_a=M_a\wedge M_r$, où $r$ est le reste de $b$ par $a$. Autrement dit : la suite des couples produits par l'algorithme d'Euclide sur $(M_b,M_a)$ est l'image, par $k\mapsto M_k$, de la suite des couples produits par l'algorithme sur $(b,a)$. Ce dernier s'arrête sur un couple $(d,0)$ avec $d=a\wedge b$ ; côté nombres de Mersenne, on aboutit à $M_d\wedge M_0=M_d\wedge 0=M_d$ (le PGCD d'un entier non nul et de $0$ est cet entier). Donc $$\left(2^a-1\right)\wedge \left(2^b-1\right)=2^{a\wedge b}-1.$$

d) Applications. $12\wedge 18=6$ (par Euclide : $18=12+6$, $12=2\times 6$), donc $\left(2^{12}-1\right)\wedge \left(2^{18}-1\right)=2^6-1=63$. On peut le vérifier sur les décompositions : $4095=3^2\cdot 5\cdot 7\cdot 13$ et $262143=3^3\cdot 7\cdot 19\cdot 73$, dont le PGCD est $3^2\cdot 7=63$.

Enfin, $M_a\mid M_b$ équivaut à $M_a\wedge M_b=M_a$, soit $M_{a\wedge b}=M_a$, soit $a\wedge b=a$ (par injectivité de $k\mapsto 2^k-1$), soit $a\mid b$. La divisibilité des nombres de Mersenne recopie exactement celle des exposants — et l'on retrouve le a) de l'exercice 1 : si $2^n-1$ est premier, ses seuls diviseurs de la forme $2^d-1$ sont $1$ et lui-même, donc $n$ n'a pas de diviseur $d$ avec $1<d<n$.

Ce que l'exercice installe. Le PGCD n'est pas qu'un nombre, c'est un algorithme, et cet algorithme descend le long de toute suite où une division euclidienne des indices se lit sur les termes. La suite de Fibonacci en est l'autre exemple classique ($F_{n+1}=1\times F_n+F_{n-1}$ est une division euclidienne, d'où $F_{n+1}\wedge F_n=1$) ; et rien ne dépend de la base $2$ — le même raisonnement vaut pour $3^a-1$, ou pour $x^a-1$ dans l'anneau des polynômes du chapitre 10.