Baccalauréat S Asie 19 juin 2014 - Correction Spécialité

Page 10 sur 10: Correction Spécialité

Spécialité 5 points

Candidats AYANT SUIVI l'enseignement de spécialité mathématiques

Partie A

Le but de celle partie est de démontrer que l'ensemble des nombres premiers est infini en raisonnant par l'absurde.

1. On suppose qu'il existe un nombre fini de nombres premiers notés $p_{1},\: p_{2}, \ldots,\: p_{n}$. On considère le nombre $E$ produit de tous les nombres premiers augmenté de 1 : \[E = p_{1} \times p~_{2} \times \cdots\times p_{n} + 1.\] Démontrer que $E$ est un entier supérieur ou égal â 2, et que $E$ est premier avec chacun des nombres $p_{1},\: p_{2}, \ldots,\: p_{n}$.
Le plus petit nombre premier est $2$.
Par conséquent $E > 2+1 \ge 2$
On a $E – p_1 \times p_2 \times \ldots \times p_n = 1$
Si $p_i$ divise $E$, puisqu’il divise également le produit $p_1 \times p_2 \times \ldots \times p_n$ il divise alors $1$.
Ce qui est impossible.
Il est donc premier avec chacun des nombres $p_1$, $p_2$,…,$p_n$.

2. En utilisant le fait que $E$ admet un diviseur premier conclure.
On en déduit donc que $E$ est un nombre premier différents de tous les $p_i$.
Ce qui est contraire à l’hypothèse qu’on avait faite.
L’ensemble des nombres premiers est donc infini.

Partie B

Pour tout entier naturel $k \geqslant 2$, on pose $M_{k} = 2^k -1$. On dit que $M_{k}$ est le $k$-ième nombre de Mersenne.

1. 1. Reproduire et compléter le tableau suivant, qui donne quelques valeurs de $M_{k}$ : $$ \begin{array}{ |c|c|c|c|c|c|c|c|c|c|}\hline k&2&3&4&5&6&7&8&9&10\\ \hline M_{k}&3&&&&&&&&\\ \hline \end{array} $$

   $k$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
   $M_k$	$3$	$7$	$15$	$31$	$63$	$127$	$255$	$511$	$1023$

   2. D'après le tableau précédent, si $k$ est un nombre premier, peut-on conjecturer que le nombre $M_{k}$ est premier ?
   Dansle tableau, si $k$ est premier ($2$,$3$,$5$ et $7$) on constate que $M_k$ l’est aussi.
2. Soient $p$ et $q$ deux entiers naturels non nuls.
   1. Justifier l'égalité : $1 + 2^p + + \left(2^p\right)^2 + \left(2^p\right)^3 + \cdots \left(2^p\right)^{q - 1} = \dfrac{\left(2^p\right)^q - 1}{2^p - 1}$.
   La somme correspond à la somme des termes d’un suite géométrique de premier terme égale à $1$ et de raison $2^p$.
   On a donc :
   $$1+2^p+(2^p)^2+\ldots+(2^p)^{q-1} = \dfrac{1 – (2^p)^q}{1 – 2^p} = \dfrac{(2^p)^q-1}{2^p-1}$$
   
   2. En déduire que $2^{pq} - 1$ est divisible par $2^p - 1$.
   b. Cela signifie donc que :
   $$(2^p-1)(1+2^p+\ldots+(2^p)^{q-1}) = (2^p)^q-1$$
   On a donc écrit $(2^p)^q-1$ en un produit de facteur dont l’un est $2^p-1$.
   Il est donc divisible par ce nombre.
   
   3. En déduire que si un entier $k$ supérieur ou égal à $2$ n'est pas premier, alors $M_{k}$ ne l'est pas non plus.
   Si $k$ est un entier supérieur ou égal à 2 non premier alors il existe $2$ entiers $p$ et $q$ tels que $k=pq$.
   Par conséquent $M_k = 2^k-1=(2^p)^q-1$ est divisible par $2^p-1$ d’après la question précédente.
   $M_k$ n’est donc pas premier.
3. 1. Prouver que le nombre de Mersenne $M_{11}$ n'est pas premier.
   $M_{11} = 2^{11} – 1 = 2047 = 23 \times 89$
   Il n’est donc pas premier.
   
   2. Que peut-on en déduire concernant la conjecture de la question 1. b. ?
   On a trouvé un nombre premier $k$ pour lequel $M_k$ n’est pas premier. La conjecture est donc fausse.

Partie C

Le test de Lucas-Lehmer permet de déterminer si un nombre de Mersenne donné est premier. Ce test utilise la suite numérique $\left(u_{n}\right)$ définie par $u_{0} = 4$ et pour tout entier naturel $n$ : \[u_{n+1} = u_{n}^2 - 2.\] Si $n$ est un entier naturel supérieur ou égal à 2, le test permet d'affirmer que le nombre $M_{n}$ est premier si et seulement si $u_{n-2} \equiv 0 \quad \text{modulo }\: M_{n}$. Cette propriété est admise dans la suite.

1. Utiliser le test de Lucas-Lehmer pour vérifier que le nombre de Mersenne $M_{ ~5}$ est premier.
$u_{5-2} = u_3 = 37634 = 31 \times 1214 \equiv 0 [31]$
Le test de Lucas-Lehmer fonctionne pour $M_5$

2. Soit $n$ un entier naturel supérieur ou égal à 3. L'algorithme suivant, qui est incomplet, doit permettre de vérifier si le nombre de Mersenne $M_{n}$ est premier, en utilisant le test de Lucas-Lehmer. $$\begin{array}{ |l|l|}\hline \text{Variables :}& u, M, n \text{ et } i \text{ sont des entiers naturels }\\ \text{Initialisation :}& u \text{ prend la valeur 4 }\\ \text{Traitement :}& \text{ Demander un entier } n \geqslant 3\\ & M \text{ prend la valeur } \ldots \ldots\\ & \text{ Pour } i \text{ allant de } 1 \text{ à } \ldots \text{faire} \\ &\quad u \text{ prend la valeur } \ldots\\ &\text{Fin Pour}\\ &\text{Si } M \text{ divise } u \text{ alors afficher «  } M \ldots \ldots \ldots \text{ » }\\ &\text{ sinon afficher «  } M \ldots \ldots \ldots \text{ » }\\ \hline \end{array}$$ Recopier et compléter cet algorithme de façon à ce qu'il remplisse la condition voulue.
Variables :
$\quad$ $u$,$M$,$n$ et $i$ sont des entiers naturels.
Initialisation :
$\quad$ $u$ prend la valeur $4$
Traitement :
$\quad$ Demander un entier $n \ge 3$
$\quad$ $M$ prend la valeur $2^n-1$
$\quad$ Pour $i$ allant de $1$ à $n-2$ faire
$\qquad$ $u$ prend la valeur $u^2-2$
$\quad$ Fin Pour
$\quad$ Si $M$ divise $u$ alors afficher « $M$ est un nombre premier »
$\qquad$ sinon afficher « $M$ n’est pas un nombre premier »