Bac S 2014 Spé Maths Asie Exercice 4

Enoncé

Partie A

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

Question 1

On suppose qu’il existe un nombre fini de nombres premiers notés p_1, p_2, …, p_n.
On considère le nombre E produit de tous les nombres premiers augmenté de 1 :

E = p_1 \times p_2 \times ... \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, …, p_n.

Démontrer par l’absurde que l’ensemble des nombres premiers est infini est un exercice tellement classique que toute cette partie A peut être considérée comme une question de cours.

En fait, le produit p_1 \times p_2 \times ... \times p_n à lui tout seul est déjà supérieur ou égal à 2 car :

  • Non seulement il est non nul :
     
     0 est divisible par 2 donc ce n’est pas un nombre premier d’où, pour tout k appartenant à \llbracket 1 ; n \rrbracket, p_k \neq 0 d’où p_1 \times p_2 \times ... \times p_n \neq 0.

    Je rappelle en effet qu’un nombre n’est pas premier dès lors qu’il admet un diviseur autre que 1 et lui-même. Comme  0 admet n’importe quel nombre entier naturel comme diviseur (ici, j’ai pris 2 mais j’aurais pu prendre 11, 641 ou encore 2017…), il n’est pas (mais alors, pas du tout) premier.

  • mais en plus, il vaut au moins 2 car :
     
    De plus, 2 est premier donc il existe un entier k appartenant à \llbracket 1 ; n \rrbracket tel que p_k = 2. Du coup, p_1 \times p_2 \times ... \times p_n est un produit d’entiers naturels non nul et qui comporte 2 en facteur : il est donc supérieur ou égal à 2.

Du coup, si le produit p_1 \times p_2 \times ... \times p_n est déjà supérieur ou égal à 2 « à lui tout seul »; E est forcément supérieur ou égal à 2 :

D’où E est supérieur ou égal à 2.

Montrons maintenant que E est premier avec chacun des nombres p_1, p_2, …, p_n. Je rappelle que :

Deux nombres a et b sont premiers entre eux si et seulement leur plus grand diviseur commun est 1 : PGCD(a;b) = 1.

Comme chacun des nombres p_1, p_2, …, p_n est un nombre premier, ils n’admettent chacun que deux diviseurs, 1 et eux-mêmes. Ainsi, les seuls diviseurs qu’ils peuvent potentiellement avoir en commun avec E, c’est 1 et eux-mêmes. Du coup, si on arrive à montrer qu’aucun d’entre eux ne divise E, le seul diviseur commun qu’ils auront avec E, ce sera 1 : 1 sera alors, de fait, le plus grand des diviseurs communs à chacun des p_k et E. Ainsi, par définition, on aura montré que chacun des p_k et E sont premiers entre eux.

Montrons donc que pour tout k \in \llbracket 1 ; n \rrbracket, p_k ne divise par E. Pour cela, il suffit de remarquer que :

Pour tout k \in \llbracket 1 ; n \rrbracket, \underbrace{E}_{dividende} = \underbrace{p_1 \times p_2 \times ... \times p_{k-1} \times p_{k+1} \times ... \times p_n}_{quotient} \times \underbrace{p_k}_{diviseur} + \underbrace{1}_{reste}.

Autrement dit :

Donc le reste de la division de E par p_k vaut 1 : aucun des p_k ne divise E.

On peut donc conclure :

Or, pour tout k \in \llbracket 1 ; n \rrbracket, les diviseurs de p_k sont 1 et p_k. Donc, le seul diviseur commun entre p_k et E est 1 : E est donc premier avec chacun des nombres p_1, p_2, …, p_n.

Question 2

En utilisant le fait que E admet un diviseur premier, conclure.

Pourquoi E admet-il un diviseur premier ?

Bonne question ! C’est une simple application du théorème suivant :

Tout entier n \geq 2 admet au moins un diviseur premier.

Or, on a montré à la question précédente que E \geq 2 donc on peut écrire :

D’après la question précédente, E \geq 2 donc il admet au moins un diviseur premier.

…ce qui est en complète contradiction avec le fait que E soit premier avec chacun des p_k.

Or, on vient de montrer que E était premier avec tous les nombres premiers p_1, p_2, …, p_n. Aucun d’entre eux n’est un diviseur de E : absurde.

D’où la conclusion :

Donc l’ensemble des nombres premiers est infini.

Je trouve l’énoncé particulièrement maladroit. Cela ne sert à rien de nous demander à la question 1 de montrer que E est premier avec chacun des p_k : il suffisait de demander de prouver qu’aucun des p_k ne divisait E : comme vous pouvez le voir, c’était la seule chose dont nous avions besoin pour conclure…


Partie B

Pour tout entier naturel k \geq 2, on pose M_k = 2^k - 1.
On dit que M_k est le k-ième nombre de Mersenne.

Question 1

a. Reproduire et compléter le tableau suivant, qui donne quelques valeurs de M_k :

Bac S 2014 Maths Spé Asie Exercice 4

Aucune difficulté ici :

Bac S 2014 Maths Spé Asie Exercice 4 2014-as-exo4s-2

b. D’après le tableau précédent, si k est un nombre premier, peut-on conjecturer que le nombre M_k est premier ?

Voyons si, dans le tableau que nous venons d’établir, M_k est premier lorsque k est premier :

M_2 = 3 est premier.
M_3 = 7 est premier.
M_5 = 31 est premier.
M_7 = 127 est premier.

On peut donc conjecturer que :

Il semblerait donc que, lorsque k est premier, M_k est premier.

Question 2

Soient p et q deux entiers naturels non nuls.

a. Justifier l’égalité : 1 + 2^p + (2^p)^2 + (2^p)^3 + ... + (2^p)^{q-1} = \dfrac{(2^p)^q - 1}{2^p - 1}.

Une telle somme doit absolument vous faire réagir et penser à…

…la somme des q premiers termes d’une suite géométrique !

Exactement :

On pose u_n la suite définie par, pour tout entier naturel n, u_n = (2^p)^n.

Montrons d’abord que (u_n) est géométrique. Pour ce faire, je rappelle que :

Pour montrer que (u_n) est une suite géométrique, il suffit de montrer que \dfrac{u_{n+1}}{u_n} = q, où q est une constante qui ne dépend pas de n.

Calculons donc \dfrac{u_{n+1}}{u_n} :

\dfrac{u_{n+1}}{u_n} = \dfrac{(2^p)^{n+1}}{(2^p)^{n}} = 2^p
Donc la suite (u_n) est géométrique de raison 2^p.

Pour continuer, il suffit de savoir que :

La somme des N premiers termes d’une suite géométrique (u_n) de raison r vaut :
\sum\limits_{k} r^k = \text{1er terme} \times \dfrac{1-r^{\text{nombre de termes}}}{1 - r}

Ici :

  • le premier terme vaut u_0 = (2^p)^0 = 1 ;
  • on calcule une somme de q termes ;

donc, en appliquant cette formule, on obtient :

Donc la somme des q premiers termes de la suite (u_n) vaut :
1 + 2^p + (2^p)^2 + (2^p)^3 + ... + (2^p)^{q-1} = \dfrac{1 - (2^p)^q}{1 - 2^p}
Hum… Ce n’est pas tout à fait le résultat de l’énoncé…

Oui, l’énoncé à juste « inversé » les signes. C’est comme si on multipliait le numérateur et le dénominateur par -1 donc on peut directement compléter notre calcul par le résultat de l’énoncé :

... = \dfrac{(2^p)^q - 1}{2^p - 1}

b. En déduire que 2^{pq} - 1 est divisible par 2^{p} - 1.

A nouveau le cours va nous être utile :

On dit que « a est divisible par b » ou que « b divise a » si et seulement si il existe q entier relatif tel que a = bq.

Le plus important, c’est de noter que q doit être un entier relatif. Nous allons donc bien prendre le soin de le remarquer :

D’après ce qui précède, on a :
(2^p)^q - 1 = 2^{pq} - 1 = (2^p - 1) \times q avec q = 1 + 2^p + (2^p)^2 + (2^p)^3 + ... + (2^p)^{q-1} entier relatif. Donc 2^{pq} - 1 est divisible par 2^p - 1.

c. 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.

Et c’est reparti pour un rappel de cours…

Tout entier supérieur ou égal à 2 non premier admet au moins un diviseur premier.

Cela nous permet d’écrire que :

Soit k un entier supérieur ou égal à 2. Il admet donc au moins un diviseur p premier. Donc k peut s’écrire sous la forme k = pq avec p supérieur ou égal à 2 (car il est premier) et q entier.

Faisons le lien avec le k-ième nombre de Mersenne :

D’où M_k = 2^k - 1 = 2^{pq} - 1.

Il est temps d’utiliser le résultat de la question précédente :

Donc, d’après la question précédente, M_k est divisible par 2^p - 1.
Ouf ! On a fini la question !

Eh non ! Qu’est-ce qui vous dit que 2^p - 1 ne vaut pas 1 ? Si c’était le cas, cela ne nous garantirait pas que M_k n’est pas premier. Heureusement, ce n’est pas le cas :

Or, p \geq 2 donc 2^p - 1 \geq 2.

Maintenant on peut conclure :

Donc M_k n’est pas premier.

Question 3

a. Prouver que le nombre de Mersenne M_{11} n’est pas premier.

Calculons M_{11} :

M_{11} = 2^{11} - 1 = 2048 - 1 = 2047

Je ne sais pas pour vous, mais moi, je ne sais pas du tout déterminer tout seul si ce nombre est premier ou non. J’ai donc utilisé ma calculatrice, et plus précisément la fonction factor de ma TI-89 :

Bac S 2014 Maths Spé Asie Exercice 4 2014-as-exo4s-3

Comme vous pouvez le voir, 2047 = 23 \times 89 donc on peut écrire :

... = 23 \times 89.
Donc M_{11} n’est pas premier.

b. Que peut-on en déduire concernant la conjecture de la question 1. b. ?

Eh oui ! Notre conjecture était fausse !

11 est premier mais M_{11} n’est pas premier donc la conjecture de la question 1. b. est 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 (u_n) 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\ \textrm{modulo}\ M_n. Cette propriété est admise dans la suite.

Question 1

Utiliser le test de Lucas-Lehmer pour vérifier que le nombre de Mersenne M_5 est premier.

D’après l’énoncé, pour savoir si M_5 est premier ou non, il suffit de voir si u_3 \equiv 0\ \textrm{modulo}\ M_5, autrement dit si u_3 est divisible par M_5. Je rappelle en effet que :

« a est divisible par b » ou « b divise a » si et seulement si a \equiv 0\ \textrm{modulo}\ b.

Calculons donc u_3 :

u_1 = u_0^2 - 2 = 4^2 - 2 = 16 - 2 = 14
 
u_2 = u_1^2 - 2 = 14^2 - 2 = 196 - 2 = 194
 
u_3 = u_2^2 - 2 = 194^2 - 2 = 37636 - 2 = 37634

Puis vérifions que u_3 est divisible par M_5 :

Or 37634 = 1214 \times 31 = 1214 \times M_5 donc M_5 est bien premier.

Question 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 :

Bac S 2014 Maths Spé Asie Exercice 4 2014-as-exo4s-4

Recopier et compléter cet algorithme de façon à ce qu’il remplisse la condition voulue.

Pour répondre à cette question, il faut bien comprendre comment est structuré l’algorithme proposé. Examinons-le donc d’un peu plus près :

Bac S 2014 Maths Spé Asie Exercice 4 2014-as-exo4s-5

  1. Ici, quatre variables sont effectivement nécessaires :
    • la première variable, u, va contenir les différents termes de la suite (u_n) sur laquelle s’appuie le test de Lucas-Lehmer. Comme (u_n) est une suite d’entiers naturels, u va contenir des entiers naturels : il doit donc être défini comme un entier naturel. Bien sûr, cette variable ne contient qu’un seul terme à la fois. Si un nouveau terme vient remplacer le précédent, ce dernier est « écrasé » et « perdu à jamais » ;
    • la deuxième variable, M, va contenir le nombre de Mersenne. Ce nombre étant un entier naturel, M va contenir des entiers naturels donc il doit être défini comme un entier naturel ;
    • la troisième variable, n, va contenir le rang du nombre de Mersenne considéré (par exemple, si n vaut 5, c’est qu’on s’intéresse à M_5). Le rang étant un entier naturel, n va contenir des entiers naturels donc il doit être défini comme un entier naturel ;
  2. On passe ensuite à l’initialisation des variables. Ici, seule u a besoin d’être initialisée car s’agissant des autres variables, on leur fait prendre des valeurs particulières dès leur première apparition dans la phase de traitement. A quoi cela servirait-il de les initialiser si c’est pour immédiatement écraser cette valeur lors de la phase de traitement ?…
     
    Du coup, pour u, la question que l’on doit se poser est la suivante : « Avec quelles valeurs est-ce que je souhaite commencer à dérouler mon algorithme ? ». Ici, le premier terme de la suite est u_0 et il vaut 4. Donc u doit valoir 4 : c’est bien ce que fait l’algorithme proposé.
     
  3. Passons maintenant à la phase de traitement :

    • Demander un entier n \geq 3

      Puisque l’algorithme doit permettre d’indiquer si un nombre de Mersenne est premier ou non, il faut bien demander à l’utilisateur le nombre de Mersenne à considérer. D’où l’instruction « Demander un entier n \geq 3 » qui signifie que l’algorithme attend que l’utilisateur saisisse une valeur et que c’est cette valeur qui va être stockée dans n ;

    • une fois que l’on sait à quel nombre de Mersenne on s’intéresse, il faut bien sûr le calculer. D’où l’instruction :
       
      M prend la valeur ……

      Et comme on cherche à calculer le nombre de Mersenne de rang n saisi par l’utilisateur, il suffit donc de compléter l’instruction par :

      M prend la valeur 2^n - 1
    • On passe ensuite au calcul de u_{n-2}. L’idée, c’est de calculer un par un les termes de la suite u_n du rang 1 au rang n - 2 en écrasant à chaque fois la valeur de la variable u. Les instructions à dérouler pour faire cela sont identiques à chaque rang, c’est pourquoi une boucle « Pour » est mise en place : elle permet de dérouler plusieurs fois le même ensemble d’instructions. Comme vous pouvez le voir, la boucle « Pour » nécessite qu’on lui précise combien de fois passer à l’intérieur en spécifiant les bornes de la variable « compteur » i :
       
      Pour i allant de 1 à … faire

      Pour compléter les pointillés ci-dessus, la question que vous devez vous poser est : « Combien de fois ai-je besoin de passer dans la boucle Pour » ? Or, pour calculer u_{n-2}, il faut qu’on calcule u_1, u_2, …, u_{n-3} et enfin u_{n-2} : il faudra donc « écraser » la variable u n-2 fois. Ainsi, il faut compléter l’instruction de la manière suivante :

      Pour i allant de 1 à n-2 faire

      Reste à savoir quelle valeur affecter à la variable u :

      u prend la valeur …

      Vous devez supposer que la valeur de u_n est stockée dans la variable u (car on a dit que u contenait les valeurs de la suite u_n) et vous demander : « A partir du terme u_n, comment est-ce que j’obtiens u_{n+1} ? ».

      Il suffit d’appliquer la relation de récurrence indiquée dans l’énoncé, non ?

      Exactement : u_{n+1} = u_n^2 - 2.
      Or, qui contient la valeur de u_n dans l’algorithme ?

      u !

      Donc, u_{n+1} s’écrit de la façon suivante en fonction des variables : u_{n+1} = u^2 - 2.
      D’où, si u contient la valeur du terme de rang n, pour remplacer sa valeur par le terme de rang suivant, il suffit de lui affecter la valeur correspondant à u^2 - 2.

      Ainsi, l’instruction doit être complétée de la façon suivante :

      u prend la valeur u^2 - 2
  4. Il reste deux instructions à compléter. Il s’agit des deux instructions d’un bloc « Si … Sinon » :
     
    Si M divise u, alors afficher « M ……… »
    sinon afficher « M ……… »

    A la sortie de la boucle « Pour », u contient u_{n-2} donc si M divise u, c’est que M_n divise u : on se trouve dans le cas u_{n-2} \equiv 0~mod~M_n, donc M est premier. Sinon, c’est que u_{n-2} n’est pas congru à 0~mod~M_n donc M n’est pas premier :

    Si M divise u, alors afficher « M est premier »
    sinon afficher « M n’est pas premier »

Fin de l’épreuve du Bac S 2014 Spé Maths Asie Exercice 4.

Exprimez vous!