Arithmétique
matT_1504_12_11C
Ens. de spécialité
36
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.
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 | |
| Affecter à k la valeur k + 1 | ||
| Fin de Tant que. | ||
| Sortie | Afficher k. Si | |
| 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 
par 
, puis celle de 
par 
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é
▶ 1. Prouver une assertion
Si 
divise 
, alors il existe un entier naturel 
tel que 
.
Si 
divise 
, alors il existe un entier naturel 
tel que 
.
Nous avons ainsi l'égalité : 
. Puisque 
, 
divise 
.
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é 
et 
sont premiers entre eux, nous déduisons du théorème de Gauss que 
divise 
. Il existe donc un entier naturel 
tel que 
.
Finalement : 
ce qui nous permet de dire que 
divise 
.
▶ 2. a) Invalider une conjecture
Si 3 divise 
et 4 divise 
alors, puisque 3 et 4 sont premiers entre eux, d'après la question 1., nous avons 
qui divise 
. 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 
, 
, 
et 
des entiers relatifs, 
un entier tel que 
.
Si 
et 
alors 
.
4 divise 
donc 
. Ensuite 
.
Par conséquent, 4 ne divise pas 
.
c) Justifier qu'un entier n'est pas divisible par 3
Notez bien
Soit 
et 
deux entiers relatifs, 
un entier tel que 
, 
un entier naturel.
Si 
alors 
.
donc 
et ainsi 
. Or 
donc 
.
Finalement 
.
Par conséquent, 3 ne divise pas 
.
d) Calculer une somme de termes consécutifs d'une suite géométrique
.
e) Démontrer qu'un entier est divisible par 7
La somme 
est obtenue en additionnant des entiers naturels donc cette somme est un entier naturel. Cela signifie par conséquent que le quotient 
est un entier naturel donc que 7 divise 
.
▶ 3. Étudier la primalité d'un entier naturel
Rappelons que, si 
est un entier naturel supérieur ou égal à 2 et si 
n'est divisible par aucun nombre premier inférieur ou égal à 
, alors 
est premier.
Nous devons examiner ici si 
est premier. Or 
. 127 est-il divisible par un nombre premier inférieur ou égal à 11 ?
127 est impair donc 127 n'est pas divisible par 2.
donc 127 n'est pas divisible par 3.
donc 127 n'est pas divisible par 5.
donc 127 n'est pas divisible par 7.
donc 127 n'est pas divisible par 11.
D'après le rappel initial, nous pouvons conclure que le nombre de Mersenne 
est un nombre premier.
▶ 4. a) Exécuter un algorithme
Exécutons l'algorithme si l'utilisateur entre 
.
Initialisation
prend la valeur 2.
Traitement
est impair donc il n'est pas divisible par 2 :
De plus, 
prend la valeur 3.
D'après la question 2. c), 
n'est pas divisible par 3.
. De plus, 
prend la valeur 4.
D'après la question 2. b), 
n'est pas divisible par 4.
. De plus, 
prend la valeur 5.
.
Or 
et 
donc 
.
Par conséquent, 
n'est pas divisible par 5 :
. De plus, 
prend la valeur 6.
n'est ni divisible par 2, ni divisible par 3.
Par conséquent, 
n'est pas divisible par 6 :
. De plus, 
prend la valeur 7.
D'après la question 2. e), 
est divisible par 7 :
.
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 
. Comme 
, il affiche ensuite « CAS 2 ».
Exécutons l'algorithme si l'utilisateur entre 
.
D'après la question 3., 
est premier.
Quelle que soit la valeur de l'entier 
, la condition 
sera toujours remplie.
La boucle Tant Que s'arrêtera donc lorsque 
sera strictement supérieur à 
.
L'algorithme affiche donc 
. Comme 
, il affiche ensuite « CAS 1 ».
Remarque. Pour un nombre de Mersenne 
donné, cet algorithme cherche à déterminer le plus petit entier 
(
) possible qui divise 
et qui est inférieur ou égal à 
.
b) Interpréter l'affichage en sortie d'un algorithme
Le « CAS 2 » signifie que le nombre de Mersenne 
n'est pas premier car l'algorithme a permis de trouver et d'afficher un nombre 
(
) plus petit diviseur de 
.
c) Interpréter l'affichage en sortie d'un algorithme
Le « CAS 1 » signifie que le nombre de Mersenne 
est premier car l'algorithme n'a pas permis de trouver et d'afficher un nombre 
(
) diviseur de 
avec 
.