Les nombres de Mersenne

Merci !

Annales corrigées
Classe(s) : Tle S | Thème(s) : Arithmétique
Type : Exercice | Année : 2015 | Académie : Pondichéry


Pondichéry • Avril 2015

Exercice 4 • 5 points

Les nombres de Mersenne

Les nombres de la forme 2n − 1 où n est un entier naturel non nul sont appelés nombres de Mersenne.

 1. On désigne par a, b et c trois entiers naturels non nuls tels que PGCD(b, c= 1.

Prouver, à l’aide du théorème de Gauss, que :

si b divise a et c divise a alors le produit bc divise a.

 2. On considère le nombre de Mersenne 233 − 1.

Un élève utilise sa calculatrice et obtient les résultats ci-dessous.

matT_1504_12_01C_04

Il affirme que 3 divise 233 − 1 et 4 divise 233 − 1 et 12 ne divise pas 233 − 1.

a) En quoi cette affirmation contredit-elle le résultat démontré à la question 1. ?

b) Justifier que, en réalité, 4 ne divise pas 233 − 1.

c) En remarquant que 2 ≡ − 1 [3], montrer que, en réalité, 3 ne divise pas 233 − 1.

d) Calculer la somme S = 1 + 23 + (23)2 + (23)3 ++ (23)10.

e) En déduire que 7 divise 233 − 1.

 3. On considère le nombre de Mersenne 27 − 1. Est-il premier ? Justifier.

 4. On donne l’algorithme suivant où MOD(N, k) représente le reste de la division euclidienne de N par k.

Variables

n entier naturel supérieur ou égal à 3

k entier naturel supérieur ou égal à 2

Initialisation

Demander à l’utilisateur la valeur de n.

Affecter à k la valeur 2.

Traitement

Tant que MOD(2n − 1, k) ≠ 0 et 239002-Eqn21

Affecter à k la valeur k + 1

Fin de Tant que.

Sortie

Afficher k.

Si 239002-Eqn22

Afficher « CAS 1 »

Sinon

Afficher « CAS 2 »

Fin de Si

a) Qu’affiche cet algorithme si on saisit n = 33 ? Et si on saisit n = 7 ?

b) Que représente le CAS 2 pour le nombre de Mersenne étudié ? Que représente alors le nombre k affiché pour le nombre de Mersenne étudié ?

c) Que représente le CAS 1 pour le nombre de Mersenne étudié ?

Les clés du sujet

Durée conseillée : 60 minutes.

Les thèmes clés

Nombres premiers • Congruences • Algorithmique • Suites géométriques.

Les outils dont vous avez besoin

Les références en rouge renvoient à la boîte à outils en fin d’ouvrage.

Somme de termes consécutifs d’une suite géométrique E4e 2. d)

Nos coups de pouce

 1. Traduisez la divisibilité de 239002-Eqn27 par 239002-Eqn28, puis celle de 239002-Eqn29 par 239002-Eqn30 avant de chercher à appliquer le théorème de Gauss.

 2. b) et c) Utilisez judicieusement les propriétés sur les congruences pour justifier les résultats demandés.

Corrigé

Corrigé

 1. Prouver une assertion

Si 239002-Eqn327 divise 239002-Eqn328, alors il existe un entier naturel 239002-Eqn329 tel que 239002-Eqn330.

Si 239002-Eqn331 divise 239002-Eqn332, alors il existe un entier naturel 239002-Eqn333 tel que 239002-Eqn334.

Nous avons ainsi l’égalité : 239002-Eqn335. Puisque 239002-Eqn336, 239002-Eqn337 divise 239002-Eqn338.

Notez bien

Si p, q et r sont trois entiers relatifs non nuls, si p divise le produit qr et si p et q sont premiers entre eux, alors p divise r.

Comme d’après l’énoncé 239002-Eqn339 et 239002-Eqn340 sont premiers entre eux, nous déduisons du théorème de Gauss que 239002-Eqn341 divise 239002-Eqn342. Il existe donc un entier naturel 239002-Eqn343 tel que 239002-Eqn344.

Finalement : 239002-Eqn345 ce qui nous permet de dire que 239002-Eqn346divise 239002-Eqn347.

 2. a) Invalider une conjecture

Si 3 divise 239002-Eqn348 et 4 divise 239002-Eqn349 alors, puisque 3 et 4 sont premiers entre eux, d’après la question 1., nous avons 239002-Eqn350 qui divise 239002-Eqn351. L’affirmation de l’élève contredit donc le résultat prouvé à la question 1.

b) Justifier qu’un entier n’est pas divisible par 4

Notez bien

Soit 239002-Eqn352, 239002-Eqn353, 239002-Eqn354 et 239002-Eqn355 des entiers relatifs, 239002-Eqn356 un entier tel que 239002-Eqn357.

Si 239002-Eqn358 et 239002-Eqn359 alors 239002-Eqn360.

4 divise 239002-Eqn361 donc 239002-Eqn362. Ensuite 239002-Eqn363.

Par conséquent, 4 ne divise pas 239002-Eqn364.

c) Justifier qu’un entier n’est pas divisible par 3

Notez bien

Soit 239002-Eqn365 et 239002-Eqn366 deux entiers relatifs, 239002-Eqn367 un entier tel que 239002-Eqn368, 239002-Eqn369 un entier naturel.

Si 239002-Eqn370 alors 239002-Eqn371.

239002-Eqn372 donc 239002-Eqn373 et ainsi 239002-Eqn374. Or 239002-Eqn375 donc 239002-Eqn376.

Finalement 239002-Eqn377.

Par conséquent, 3 ne divise pas 239002-Eqn378.

d) Calculer une somme de termes consécutifs d’une suite géométrique

239002-Eqn379.

e) Démontrer qu’un entier est divisible par 7

La somme 239002-Eqn380 est obtenue en additionnant des entiers naturels donc cette somme est un entier naturel. Cela signifie par conséquent que le quotient 239002-Eqn381 est un entier naturel donc que 7 divise 239002-Eqn382.

 3. Étudier la primalité d’un entier naturel

Rappelons que, si 239002-Eqn383 est un entier naturel supérieur ou égal à 2 et si 239002-Eqn384 n’est divisible par aucun nombre premier inférieur ou égal à 239002-Eqn385, alors 239002-Eqn386 est premier.

Nous devons examiner ici si 239002-Eqn387 est premier. Or 239002-Eqn388. 127 est-il divisible par un nombre premier inférieur ou égal à 11 ?

127 est impair donc 127 n’est pas divisible par 2.

239002-Eqn389 donc 127 n’est pas divisible par 3.

239002-Eqn390 donc 127 n’est pas divisible par 5.

239002-Eqn391 donc 127 n’est pas divisible par 7.

239002-Eqn392 donc 127 n’est pas divisible par 11.

D’après le rappel initial, nous pouvons conclure que le nombre de Mersenne 239002-Eqn393est un nombre premier.

 4. a) Exécuter un algorithme

Exécutons l’algorithme si l’utilisateur entre 239002-Eqn394.

Initialisation

239002-Eqn395 prend la valeur 2.

Traitement

239002-Eqn396 est impair donc il n’est pas divisible par 2 :239002-Eqn397

De plus, 239002-Eqn398 prend la valeur 3.

D’après la question 2. c), 239002-Eqn399 n’est pas divisible par 3.

239002-Eqn400. De plus, 239002-Eqn401 prend la valeur 4.

D’après la question 2. b), 239002-Eqn402 n’est pas divisible par 4.

239002-Eqn403. De plus, 239002-Eqn404 prend la valeur 5.

239002-Eqn405.

Or 239002-Eqn406 et 239002-Eqn407 donc 239002-Eqn408.

Par conséquent, 239002-Eqn409 n’est pas divisible par 5 :

239002-Eqn410. De plus, 239002-Eqn411 prend la valeur 6.

239002-Eqn412 n’est ni divisible par 2, ni divisible par 3.

Par conséquent, 239002-Eqn413 n’est pas divisible par 6 :

239002-Eqn414. De plus, 239002-Eqn415 prend la valeur 7.

D’après la question 2. e), 239002-Eqn416 est divisible par 7 :

239002-Eqn417.

L’une des conditions de la boucle « Tant Que » n’est plus vérifiée.

Cette boucle s’arrête donc.

Sortie

L’algorithme affiche 239002-Eqn418. Comme 239002-Eqn419, il affiche ensuite « CAS 2 ».

Exécutons l’algorithme si l’utilisateur entre 239002-Eqn420.

D’après la question 3., 239002-Eqn421 est premier.

Quelle que soit la valeur de l’entier 239002-Eqn422, la condition 239002-Eqn423sera toujours remplie.

La boucle Tant Que s’arrêtera donc lorsque 239002-Eqn424 sera strictement supérieur à 239002-Eqn425.

L’algorithme affiche donc 239002-Eqn426. Comme 239002-Eqn427, il affiche ensuite « CAS 1 ».

Remarque. Pour un nombre de Mersenne 239002-Eqn428 donné, cet algorithme cherche à déterminer le plus petit entier 239002-Eqn429 (239002-Eqn430) possible qui divise 239002-Eqn431 et qui est inférieur ou égal à 239002-Eqn432.

b) Interpréter l’affichage en sortie d’un algorithme

Le « CAS 2 » signifie que le nombre de Mersenne 239002-Eqn433n’est pas premier car l’algorithme a permis de trouver et d’afficher un nombre 239002-Eqn434 (239002-Eqn435) plus petit diviseur de 239002-Eqn436.

c) Interpréter l’affichage en sortie d’un algorithme

Le « CAS 1 » signifie que le nombre de Mersenne 239002-Eqn437est premier car l’algorithme n’a pas permis de trouver et d’afficher un nombre 239002-Eqn438 (239002-Eqn439) diviseur de 239002-Eqn440 avec 239002-Eqn441.