mathématiques MPSI · Chapitre 7 · Exercice de TD

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

Arithmétique dans l'ensemble des entiers relatifs · B. PGCD, algorithme d'Euclide, Bézout · niveau 3 (difficile)

Énoncé

Pour $k \in N$ , on note $M_{k} = 2^{k} - 1$ .

a) Montrer que si $a$ divise $b$ , alors $M_{a}$ divise $M_{b}$ .

b) Soient $a \geq 1$ et $b \geq 0$ , et $b = a q + r$ la division euclidienne de $b$ par $a$ . Montrer que $M_{r}$ est le reste de la division euclidienne de $M_{b}$ par $M_{a}$ .

c) En déduire, par l'algorithme d'Euclide, que $M_{a} \land M_{b} = M_{a \land b}$ pour tous $a, b \in N^{*}$ .

d) Application : calculer $(2^{12} - 1) \land (2^{18} - 1)$ , et montrer que $M_{a}$ divise $M_{b}$ si et seulement si $a$ divise $b$ .

Corrigé de la question 1

La stratégie. L'algorithme d'Euclide repose sur un seul lemme : si $b = a q + r$ , alors $b \land a = a \land 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 N$ , alors, avec $x = 2^{a}$ et $d = k$ dans l'identité $x^{d} - 1 = (x - 1) (x^{d - 1} + \dots + 1)$ : $M_{b} = 2^{ak} - 1 = (2^{a} - 1) (2^{a (k - 1)} + 2^{a (k - 2)} + \dots + 2^{a} + 1),$ et le second facteur est un entier. Donc $M_{a} ∣ M_{b}$ . (Pour $k = 0$ , $M_{0} = 0$ est divisible par tout.)

Question 2 : comment l'IA t'aide

b) Soient $a \geq 1$ et $b \geq 0$ , et $b = a q + r$ la division euclidienne de $b$ par $a$ . Montrer que $M_{r}$ est le reste de la division euclidienne de $M_{b}$ par $M_{a}$ .

Élève

Pour le b), j'ai $2^{a} \equiv 1 (mod M_{a})$ , donc $2^{a q} \equiv 1$ et $2^{b} = 2^{a q} 2^{r} \equiv 2^{r}$ , ce qui donne $M_{b} \equiv M_{r} (mod M_{a})$ . Est-ce que ça suffit pour dire que $M_{r}$ est le reste ?

Ta congruence est juste. Mais une infinité d'entiers sont congrus à $M_{b}$ modulo $M_{a}$ : qu'est-ce qui distingue le reste de la division euclidienne parmi eux ?

Élève

Le reste est le seul de ces entiers qui soit compris entre $0$ et $M_{a} - 1$ . Il faut donc que je situe $M_{r}$ par rapport à $M_{a}$ avant de conclure.

C'est le point qui manque. Qu'est-ce que la division $b = a q + r$ t'apprend sur $r$ , et par quelle propriété de $k \mapsto 2^{k} - 1$ peux-tu transporter cette information jusqu'à $M_{r}$ , y compris quand $r = 0$ ?

L'IA ne donne pas la réponse : elle pose la question qui fait avancer. À toi de continuer.

Continue cet exercice avec l'IA

Reprends la question 2 là où le dialogue s'arrête, puis la suite de l'exercice.

Continuer avec l'IA — gratuit, sans inscription

Gratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.

Le cours du chapitre · Tous les exercices du chapitre

Continuer avec l'IA, gratuit →

Euclide à l'étage des exposants : (2a−1)∧(2b−1)=2a∧b−1

Énoncé

Corrigé de la question 1

Question 2 : comment l'IA t'aide

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