Exercice 41

Pour $k\in\mathbb{N}$, posons $N_{k}=a^{k}-1$. On a $N_{0}=0$, et la suite $(N_{k})$ est strictement croissante car $a\geqslant 2$. L'exercice 31 du chapitre 1 établit que, si $n=mq+r$ avec $0\leqslant r<m$, alors : $$N_{n}=N_{m}\times Q+N_{r} \qquad \text{avec} \qquad 0\leqslant N_{r}<N_{m}$$ pour un certain entier $Q$. Autrement dit, le reste de la division de $N_{n}$ par $N_{m}$ est $N_{r}$, où $r$ est le reste de la division de $n$ par $m$.

Supposons $n>m$, le cas $n=m$ étant immédiat et le cas $n<m$ s'y ramenant par symétrie. D'après la Proposition 2, $\mathrm{PGCD}(N_{n},N_{m})=\mathrm{PGCD}(N_{m},N_{r})$. Appliquons l'algorithme d'Euclide aux exposants : $n$, $m$, $r_{0}=r$, $r_{1}$, …, jusqu'au dernier reste non nul $g=\mathrm{PGCD}(m,n)$, suivi de $0$. À chaque étape, les nombres $N$ correspondants suivent exactement le même schéma : $$\mathrm{PGCD}(N_{n},N_{m})=\mathrm{PGCD}(N_{m},N_{r_{0}})=\mathrm{PGCD}(N_{r_{0}},N_{r_{1}})=\cdots$$

$$\cdots=\mathrm{PGCD}(N_{g},N_{0})=\mathrm{PGCD}(N_{g},0)=N_{g}$$ d'après la Proposition 1 pour la dernière égalité. $$\boxed{\mathrm{PGCD}\left(a^{m}-1,a^{n}-1\right)=a^{\mathrm{PGCD}(m,n)}-1}$$ On retrouve la question 3 de l'exercice 28 : $\mathrm{PGCD}(4^{n+1}-1,4^{n}-1)=4^{\mathrm{PGCD}(n+1,n)}-1=4^{1}-1=3$. Autre exemple : $\mathrm{PGCD}(2^{12}-1,2^{18}-1)=2^{6}-1=63$, ce que l'on vérifie avec $4095=63\times 65$ et $262\,143=63\times 4161$.