Exercice 56

1. D'après le chapitre 3 (proposition 5), $a^{n} - 1 = (a - 1)(a^{n - 1} + a^{n - 2} + \cdots + 1)$.

2. Si $a^{n} - 1$ est premier, son diviseur $a - 1$ vaut $1$ ou $a^{n} - 1$ ; le second cas est exclu car $n \geqslant 2$ et $a \geqslant 2$ donnent $a^{n} > a$. Donc $a = 2$. Si $n = kl$ avec $1 < k < n$, la question 1 appliquée à $(2^{k})^{l} - 1$ montre que $2^{k} - 1$ divise $2^{n} - 1$, avec $1 < 2^{k} - 1 < 2^{n} - 1$ : c'est exclu, donc $n$ est premier. $$\boxed{a = 2 \text{ et } n \text{ premier}}$$

3. On écrit $a = bq + r$ avec $0 \leqslant r < b$. Alors $$2^{a} - 1 = 2^{r}\big(2^{bq} - 1\big) + 2^{r} - 1.$$ D'après la question 1, appliquée à $(2^{b})^{q} - 1$, l'entier $2^{b} - 1$ divise $2^{bq} - 1$, et $0 \leqslant 2^{r} - 1 < 2^{b} - 1$. Par unicité de la division euclidienne, $2^{r} - 1$ en est le reste.

4. La question 3 et la proposition 4 donnent $(2^{a} - 1) \wedge (2^{b} - 1) = (2^{b} - 1) \wedge (2^{r} - 1)$ : le couple $(2^{a} - 1, 2^{b} - 1)$ suit pas à pas l'algorithme d'Euclide appliqué à $(a, b)$, comme les nombres de Fibonacci de l'exercice 23. Par récurrence forte sur $b$, en admettant $b \geqslant 1$ et $r \geqslant 0$, l'algorithme s'arrête sur le couple $(2^{d} - 1, 2^{0} - 1) = (2^{d} - 1, 0)$, avec $d = a \wedge b$. $$\boxed{(2^{a} - 1) \wedge (2^{b} - 1) = 2^{a \wedge b} - 1}$$ Par exemple, $(2^{12} - 1) \wedge (2^{18} - 1) = 4095 \wedge 262\,143 = 63 = 2^{6} - 1$. ✓