Le sujet de mathématiques pour séries S proposait en exercice pour spécialistes un travail sur les nombres de Mersenne et un algorithme.4)a) Pour savoir ce que répond cet algorithme, programmons-le sur notre calculatrice graphique :
Algorithme | Programme | ||||||||||||
|
 
Attention : L'exécution avec n=33 prend étrangement 2min30s sur fx-CP400. La réponse était pourtant quasiment immédiate sur tous les autres modèles.
|
D'après notre calculatrice graphique, l'algorithme affiche donc :
- pour k=33 :
7
CAS 2 - pour k=7 :
12
CAS 1
4)b) L'algorithme se termine si l'on sort de la boucle 'Tant que'. Si cette boucle se termine, c'est que la condition de poursuite
$mathjax$MOD(2^n-1,k)≠0~et~k≤\sqrt{2^n-1}$mathjax$
n'est plus vérifiée, et qu'il y a réalisation de son contraire $mathjax$MOD(2^n-1,k)=0~ou~k>\sqrt{2^n-1}$mathjax$
.Autrement dit, la boucle 'Tant que' se termine sur la réalisation d'une des deux conditions suivantes :
- $mathjax$MOD(2^n-1,k)=0$mathjax$
- $mathjax$k>\sqrt{2^n-1}$mathjax$
Dans le cas n°2, on n'a pas
$mathjax$k>\sqrt{2^n-1}$mathjax$
puisque nous sommes dans le bloc 'sinon' de l'instruction conditionnelle, et nous avons donc pas conséquent le contraire $mathjax$k≤\sqrt{2^n-1}$mathjax$
.Donc forcément, la boucle s'est terminée sur la réalisation de l'autre condition
$mathjax$MOD(2^n-1,k)=0$mathjax$
.Le nombre k trouvé par l'algorithme vérifiant donc
$mathjax$MOD(2^n-1,k)=0$mathjax$
et $mathjax$k≤\sqrt{2^n-1}$mathjax$
est tout simplement le plus petit diviseur différent de 1 du nombre de Mersenne $mathjax$2^n-1$mathjax$
.Comme ce diviseur a été trouvé, le nombre de Mersenne
$mathjax$2^n-1$mathjax$
considéré n'est donc pas premier.4)c) Dans le cas n°1, nous avons
$mathjax$k>\sqrt{2^n-1}$mathjax$
.Or, les diviseurs du nombre de Mersenne
$mathjax$2^n-1$mathjax$
différents de ce même nombre sont forcément inférieurs ou égaux à $mathjax$\sqrt{2^n-1}$mathjax$
.Aucun diviseur répondant à ces critères n'ayant été trouvé, le nombre de Mersenne
$mathjax$2^n-1$mathjax$
considéré est donc premier.Liens :
.
