Sujet 7Arithmétique, algorithme1 heure
Inde, avril 2015
Arithmétique
Algorithmique
Exercice
5 ptsLes 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. 0,5 pt
2 On considère le nombre de Mersenne 233 – 1.
Un élève utilise sa calculatrice et obtient les résultats ci-dessous.
(233 – 1) ÷ 3 | |
2863311530 | |
(233 – 1) ÷ 4 | |
2147483648 | |
(233 – 1) ÷ 12 | |
715827882,6 |
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 ? 0,5 pt
b. Justifier que, en réalité, 4 ne divise pas (233 – 1). 0,5 pt
c. En remarquant que 2 ≡ – 1[3], montrer que, en réalité, 3 ne divise pas 233 – 1. 0,5 pt
d. Calculer la somme S = 1 + 23 + (23)2 + (23)3 + … + (23)10. 0,5 pt
e. En déduire que 7 divise (233 – 1). 0,5 pt
3 On considère le nombre de Mersenne 27 – 1. Est-il premier ? Justifier. 0,5 pt
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 ? 0,5 pt
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é ? 0,5 pt
c. Que représente le CAS 1 pour le nombre de Mersenne étudié ? 0,5 pt
Voir le corrigé
ou aux acheteurs de livres ABC du Bac
Pour approfondir le thème...
