Bac S 2015 Spé Maths Pondichéry Exercice 4

Enoncé

Les nombres de la forme 2^n - 1n est un entier naturel non nul sont appelés nombres de Mersenne.

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

Oh la belle question de cours ! Avant de commencer, j’aimerais juste vous rappeler le théorème de Gauss :

Théorème de Gauss
Soient a, b et c trois entiers relatifs non nuls.
Si a divise le produit bc et si a est premier avec b, alors a divise c.

Ce rappel étant fait, allons-y !

Commençons par interpréter le fait que c divise a. Je rappelle que :

Soient a et b deux entiers relatifs.
Dire que b divise a, c’est dire qu’il existe un entier relatif k tel que a = kb.

Ici, cela donne :

Par hypothèse, c divise a donc il existe k \in \mathbb{Z} tel que a = kc.
De la même façon, il faut aussi traduire le fait que b divise a, non ?

Même pas ! Cela ne sert à rien. En fait, tout ce qu’il faut remarquer, c’est que du coup, comme b divise lui aussi a, mais que a s’écrit kc, alors b divise kc :

Or, par hypothèse également, b divise a donc, b divise kc.

Maintenant, on va utiliser le théorème de Gauss, comme suggéré par l’énoncé :

Or, d’après l’énoncé, b et c sont premiers entre eux donc, d’après le théorème de Gauss, b divise k.

Cette fois-ci, il est effectivement pertinent de traduire ce que veut dire cette divisibilité :

Donc, il existe k tel que k = k.

On peut alors faire le lien avec a :

On en déduit que a = kc = \underbrace{k.

Ainsi, on a trouvé un entier relatif, en l’occurence k, tel que a = k. On peut donc conclure :

Donc bc divise a.

Question 2

On considère le nombre de Mersenne 2^{33} - 1.
Un élève utilise sa calculatrice et obtient les résultats ci-dessous.

Bac S 2015 Spé Maths Pondichéry Exercice 4 2015-po-exo4s-1

Il affirme que 3 divise 2^{33} - 1 et 4 divise 2^{33} - 1 et 12 ne divise pas 2^{33} - 1.

a. En quoi cette affirmation contredit-elle le résultat démontré à la question 1.?

Facile ! L’élève dit que 12 ne divise pas 2^{33} - 1. Or, d’après la question 1., si 3 et 4 divisent tous les deux 2^{33} - 1, alors leur produit 3 \times 4 = 12 divise 2^{33} - 1 !

Exactement… MAIS pour avoir tous les points à cette question, il faut préciser que 3 et 4 sont premiers entre eux :

3 et 4 sont premiers entre eux donc, si 3 et 4 divisent tous les deux 2^{33} - 1, alors leur produit 3 \times 4 = 12 divise 2^{33} - 1. Cela est en contradiction avec l’affirmation de l’élève.
C’est quand même bizarre ! D’après l’affichage de la calculatrice, on dirait vraiment que l’élève a raison puisqu’on obtient des entiers quand on divise 2^{33} - 1 par 3 et par 4, mais pas par 12 !

Ah bah voilà de l’esprit critique ! C’est bien, ça ! En fait, on voit des entiers sur la calculatrice parce qu’elle a arrondi les résultats. Essayez sur la votre pour voir !

b. Justifier que, en réalité, 4 ne divise pas 2^{33} - 1.

La justification tient au fait que :

Un nombre pair ne peut pas diviser un nombre impair.

Il faut donc écrire :

2^{33} est pair donc 2^{33} - 1 est impair. Donc 4, qui est pair, ne peut diviser 2^{33} - 1.

c. En remarquant que 2 \equiv -1 \quad [3], montrer que, en réalité, 3 ne divise pas 2^{33} - 1.

Tout d’abord, il faut bien sûr connaître le lien entre divisibilité et congruence :

Soient a et b deux entiers relatifs.
b divise a si et seulement si a \equiv 0 \quad [b].

Ici, il s’agit donc de montrer que 2^{33} - 1 n’est pas congru à  0 modulo 3. Pour cela, on va d’abord avoir besoin du rappel suivant :

Soient a, b et p des entiers relatifs, et n entier naturel.
a \equiv b \quad [p] \Rightarrow a^n \equiv b^n \quad [p]

On en tire :

2 \equiv -1 \quad [3] \Rightarrow 2^{33} \equiv (-1)^{33} \quad [3]

Or :

(-1)^{\text{un nombre pair}} = 1 et (-1)^{\text{un nombre impair}} = -1

On peut donc poursuivre :

... \Rightarrow 2^{33} \equiv -1 \quad [3]

Cette fois-ci, un deuxième rappel de cours va être utile :

Soient a, b et c des entiers relatifs, et n entier naturel.
a \equiv b \quad [n] \Rightarrow a + c \equiv b + c \quad [p]

Autrement dit :

On peut ajouter un entier relatif « membre-à-membre » dans une relation de congruence.

Ici, nous allons donc ajouter -1 « membre-à-membre » :

... \Rightarrow 2^{33} - 1 \equiv -1 - 1 \quad [3]

\Rightarrow 2^{33} - 1 \equiv -2 \quad [3]

2^{33} - 1 n’est donc pas congru à  0 modulo 3, donc, n’est pas divisible par 3 :

Donc 3 ne divise pas 2^{33} - 1.

d. Calculer la somme S = 1 + 2^3 + (2^3)^2 + (2^3)^3 + ... + (2^3)^{10}.

Le calcul de cette somme ne doit avoir aucun secret pour vous :

Soient n un entier naturel et q un réel différent de 1.
1 + q + q^2 + ... + q^n = \dfrac{1 - q^{n+1}}{1 - q}

Ici, c’est :

  • 2^3 qui joue le rôle de q ;
  • 10 qui joue le rôle de n.

Donc :

S = 1 + 2^3 + (2^3)^2 + (2^3)^3 + ... + (2^3)^{10} = \dfrac{1 - (2^3)^{11}}{1 - 2^3} = \dfrac{1 - 2^{33}}{-7} = \dfrac{2^{33} - 1}{7} = 1227133513

e. En déduire que 7 divise 2^{33} - 1.

Là, ce qu’il convient de remarquer, c’est que S est une somme d’entiers naturels donc, est un entier naturel :

D’après la question précédente, S = \dfrac{2^{33} - 1}{7} donc 2^{33} - 1 = 7S, avec S entier naturel.
Donc 7 divise 2^{33} - 1.

Question 3

On considère le nombre de Mersenne 2^7 - 1. Est-il premier ? Justifier.

L’un des moyens de voir si un nombre n est premier ou pas, est de le diviser par tous les entiers compris entre 2 et \sqrt{n}. Si on ne trouve aucun diviseur à n parmi tous ces entiers, alors n est premier.

C’est d’ailleurs, comme on le verra après, ce que fait l’algorithme de la question suivante…

Ici, 2^7 - 1 = 127 donc on peut écrire :

2^7 - 1 = 127. Or \sqrt{127} \simeq 11,3 et 127 n’est divisible par aucun entier compris entre 2 et 11 donc 2^7 - 1 est bien un nombre premier.

Question 4

On donne l’algorithme suivant où MOD(N, k) représente le reste de la division euclidienne de N par k.

Bac S 2015 Spé Maths Pondichéry Exercice 4 2015-po-exo4s-2

a. Qu’affiche cet algorithme si on saisit n = 33 ? Et si on saisit n = 7 ?

Toute l’idée de cet algorithme est de déterminer si le nombre de Mersenne 2^n-1 est premier ou non, où n est un entier naturel supérieur ou égal à 3 saisi par l’utilisateur. Pour cela, il examine le reste de la division euclidienne de 2^n-1 par chacun des entiers compris entre 2 et \sqrt{n}. Détaillons-le pas-à-pas :

  1. Variables
     
    Deux variables sont effectivement nécessaires :
     

    • la première variable, n, va contenir la valeur correspondant à la puissance n dans 2^n - 1. Cette valeur est un nombre entier supérieur ou égal à 3 saisi par l’utilisateur. Elle ne bougera pas tout au long de l’algorithme, et comme elle va contenir un entier naturel, elle doit être définie comme telle ;
    • la seconde variable, k, va elle contenir chacun des entiers compris entre 2 et \sqrt{2^n-1} avec lequel on va examiner la congruence de 2^n-1 : il est donc lui aussi défini comme un entier naturel.
       
  2. Initialisation
     
    On passe ensuite à l’initialisation des variables qui ont été créées à l’étape 1. La question que l’on doit se poser est la suivante : « Avec quelles valeurs est-ce que je souhaite commencer à dérouler mon algorithme ? » :

    • n est saisi par l’utilisateur d’où l’instruction « Demander à l’utilisateur la valeur de n » ;
    • k contient le tout premier entier par lequel on souhaite diviser 2^n-1, à savoir 2, d’où l’instruction « Affecter à k la valeur 2 ».
  3. Traitement
     
    Passons maintenant à la phase de traitement.
    L’idée, c’est, comme on l’a dit, de diviser 2^n-1 par chacune des valeurs de k tant que :

    • on n’a pas trouvé de diviseur à 2^n - 1, c’est-à-dire que MOD(2^n - 1;k) \neq 0 ;
    • et que k n’a pas dépassé la valeur \sqrt{2^n - 1}.

    D’où la condition « Tant que MOD(2^n - 1, k) \neq 0 et k \leq \sqrt{2^n - 1} ».

    Reste à savoir ce qu’il faut faire dans cette boucle.

    Eh bien c’est assez simple : il suffit d’ajouter 1 à la variable k à chaque passage dans la boucle « Tant que ». Comme ça, quand on réexamine la condition de la boucle « Tant que », on est passé à l’entier suivant.

  4. Sortie
     
    Une fois qu’on est sorti de la boucle, d’abord on affiche k. Mais ce qui m’intéresse surtout, c’est qu’on affiche ensuite « CAS 1 » ou « CAS 2 » en s’appuyant sur une structure conditionnelle « Si … Sinon ». Toute la question est de savoir quand est-ce qu’on affiche « CAS 1 » et quand est-ce qu’on affiche « CAS 2 ».

    Ce qu’il faut bien comprendre, c’est que, si on est sorti de la boucle « Tant que » de la phase de traitement, c’est que deux choses ont pu se passer :

    • soit k ~\textgreater ~\sqrt{2^n - 1}, auquel cas la variable k a dépassé la valeur \sqrt{2^n - 1} (il vaut alors le premier entier strictement supérieur à \sqrt{2^n - 1}) et donc aucun entier k compris entre 2 et \sqrt{2^n - 1} ne divisait 2^n - 1. Dans ce cas, votre cours vous dit que 2^n - 1 est premier ;
    • soit MOD(2^n - 1, k) = 0 sans que k n’ait dépassé la valeur \sqrt{2^n - 1} : dans ce cas, la valeur contenue dans k est un diviseur de 2^n - 1 et 2^n - 1 n’est donc pas premier.

Maintenant que l’on a compris tout cela, on peut répondre à la question. On sait que 2^{33} - 1 n’est pas premier, et que 2^7 - 1 l’est donc :

Cet algorithme teste la primalité de 2^n - 1n est un entier saisi par l’utilisateur en le divisant par tous les entiers compris entre 2 et \sqrt{2^n - 1} :

  • si 2^n - 1 est premier, alors il affiche le premier entier k strictement supérieur à \sqrt{2^n - 1} puis « CAS 1 » ;
  • si 2^n - 1 n’est pas premier, alors il affiche le premier diviseur k trouvé compris entre 2 et \sqrt{2^n - 1} puis « CAS 2 ».

Or, on sait d’après les questions précédentes que :

  • 2^{33} - 1 est divisible par 7, sans l’être par 2, 3, 4, 5 et 6 donc l’algorithme affiche 7 et « CAS 2 » ;
  • 2^{7} - 1 est premier et \sqrt{127} \simeq 11,3 donc l’algorithme affiche 12 et « CAS 1 ».

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é ?

Pas de difficulté particulière une fois que l’on a bien compris l’algorithme :

Le CAS 2 correspond au cas où 2^n - 1 n’est pas premier. Dans ce cas, le nombre k affiché correspond au premier diviseur qu’on lui trouve, compris entre 2 et \sqrt{2^n - 1}.

c. Que représente le CAS 1 pour le nombre de Mersenne étudié ?

Toujours pas de difficulté particulière une fois que l’on a bien compris l’algorithme :

Le CAS 1 correspond au cas où 2^n - 1 est premier.

Fin de l’épreuve du Bac S 2015 Spé Maths Pondichéry Exercice 4.

Exprimez vous!