Exercice corrigé : Nombres de Mersenne

Voici l’énoncé d’un exercice assez classique que nous allons corriger à propos des nombres de Mersenne. C’est un exercice qu’on va mettre dans le chapitre de l’arithmétique autour des nombres premiers. C’est un exercice faisable en première année dans le supérieur dès lors qu’on a fait de l’arithmétique. En voici l’énoncé :

Et voici maintenant la première question !

Question 1

Montrons plutôt la contraposée, c’est à dire. Si a ≠ 2 ou n n’est pas premier alors aⁿ – 1 n’est pas premier.

Premier cas : a ≠ 2

Dans ce cas, on utilise la formule qu’on a donnée dans le chapitre des identités remarquables :

a^n-1 = (a-1)\sum_{k=0}^{n-1} a^k

On a :

a-1 \geq 2

Et

\sum_{k=0}^{n-1} a^k \geq 1 +a \geq 2 

Donc on a trouvé 2 facteurs strictement supérieurs à 1 permettant de décomposer a^n- 1 en deux diviseurs. Donc a^n - 1 n’est pas premier.

Cas n non premier

Dans ce cas, il existe d et k tous les deux supérieurs ou égaux à 2 tels que : n = dk
On a alors, en utilisant toujours la même formule

a^n-1 = (a^{d})^k -1 = (a^d-1)\sum_{i=0}^{k-1}a^{di}

Et là aussi :

a^d - 1  \geq 2^2 -1 =3

Pour le second facteur, on a aussi :

\sum_{i=0}^{k-1}a^{di} \geq 1 + a^d \geq 1 +2^2 = 5

On a donc décomposé ce nombre comme le produit de deux entiers supérieurs ou égaux à 2. Donc là aussi, il n’est pas premier.

Question 2

Tout simplement, calculons explicitement ces nombres pour montrer qu’ils sont premiers.

• M₂ = 2² – 1 = 3 est premier
• M₃ = 2³ – 1 = 7 est premier
• M₅ = 2⁵ – 1 = 31 est premier
• M₇ = 2⁷ – 1 = 127 est premier (2, 3, 5, 7, 11 ne le divisent pas)

En revanche, M₁₁ n’est pas premier. En effet : M₁₁ = 2¹¹ – 1 = 2047 = 23 x 89. Donc tous les nombres de Mersenne ne sont pas premiers.

Anecdote

On connait actuellement 48 nombres de Mersenne de manière sûre :

M₂, M₃, M₅, M₇, M₁₃, M₁₇, M₁₉, M₃₁, M₆₁, M₈₉, M₁₂₇, M₅₂₁, M₆₀₇, M_{1 279}, M_{2 203}, M_{2 281}, M_{3 217}, M_{4 253}, M_{9 689}, M_{9 941}, M_{11 213}, M_{19 937}, M_{21 701}, M_{23 209}, M_{44 497}, M_{86 243}, M_{110 503}, M_{132 049}, M_{216 091}, M_{756 839}, M_{859 433}, M_{1 257 787,} M_{1 398 269}, M_{2 976 221}, M_{3 021 377}, M_{6 972 593}, M_{13 466 917}, M_{20 996 011}, M_{24 036 583}, M_{25 964 951}, M_{30 402 457}, M_{32 582 657}, M_{37 156 667}, M_{42 643 801}, M_{43 112 609}, M_{57 885 161}.

La correction en vidéo

Et pour ceux qui préfèrent, voici la correction en vidéo !

Et c’est terminé pour cet exercice assez court ! Cet exercice vous a plu ?