Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques LycéeOn parle exclusivement de maths, niveau lycée. TerminaleForum de terminale ArithmétiqueTopics traitant de Arithmétique [tout]Lister tous les topics de mathématiques

1 2 +

Niveau terminale
Partager :

Nombres de Mersenne.

Posté par Profil muriellesym 06-05-20 à 21:30

Bonjour, j'ai un problème avec l'exercice suivant :

Les nombres de la forme 2^n-1
pour n entier naturel s'appellent les nombres de Mersenne.
Leurs diviseurs possèdent des propriétés particulières et il existe un test de primalité spécifique à ces nombres, ce qui explique l'intérêt qu'on leur porte dans la recherche des nombres premiers.
On posera dans la suite M_n = 2^n-1 (n \in \mathbb{N}).

A. Exploration

1. Pour 0 \le  n \le 20, déterminer si M_n est premier ou composé. Qu'observe-t-on quand n est composé? Quand n est premier?

2. Vérifier que, pour tout entier naturel n non nul, a^n-1 = (a-1)(a^{n-1}+a^{n-2}+...+1)
En déduire que : (n composé) implique (M_n composé)

3. On suppose que M_n admet un diviseur premier d. Justifier que 2^n \equiv 1 [d]


B. Etude du cas où p est premier
On considère un entier p premier tel que M_p = 2^p-1 admette un diviseur premier d. Soit I l'ensemble des entiers naturels n non nuls tels que 2^n \equiv 1[d]

1. Justifier que I n'est pas vide puis qu'il admet un plus petit élément p_0 et que  p_0 > 1

2. En écrivant la division euclidienne de n par  p_0 , montrer que tout élément de I est multiple de  p_0 .
En déduire que p = p_0 .

3. On admet que 2^{d-1} \equiv 1 [d]
Déduire comme en 2. que p_0 divise d-1 puis qu'il existe k (entier naturel) tel que d = 2kp+1.

\noindent\rule{2cm}{0.4pt}

Je suis bloquée à la question B.1, pouvez-vous essayer de me mettre sur la voie ?

Merci de votre aide

Posté par
carpediemre : Nombres de Mersenne. 06-05-20 à 22:55

salut

si d divise 2^p - 1 alors p est un élément de I donc I n'estpas vide ...

Posté par Profil muriellesymre : Nombres de Mersenne. 07-05-20 à 08:07

Oui mais ça me paraît un peu trop simple comme réponse, c'est juste une citation de l'énoncé de la question. Mais bon, c'est certainement ça.

Posté par
carpediemre : Nombres de Mersenne. 07-05-20 à 08:21

ben il faut finir la question maintenant ...

Posté par Profil muriellesymre : Nombres de Mersenne. 07-05-20 à 09:26

Oui,  toute partie non vide de \mathbb{N} admet un plu petit élément donc I admet un plus petit élément, p_0

Posté par Profil muriellesymre : Nombres de Mersenne. 08-05-20 à 09:53

2. En écrivant la division euclidienne de n par  p_0 , montrer que tout élément de I est multiple de  p_0 . En déduire que p = p_0 .
--

On a   n = p_0 \times q +r   avec   0 \le r < p_0   et   q\in \mathbb{N}

D'autre part, on cherche à montrer que "tout élément de I est multiple de p_0".   Les éléments de I sont les n \in \mathbb{N^*} tels que 2^n \equiv 1 [d] \iff 2^n = 1 + d \times k, k \in \mathbb{Z} \iff n = \log_2(1+d \times k).
Donc, on cherche à montrer que  p_0 | \log_2(1+d \times k), mais je ne vois pas vraiment comment faire.

Posté par
Sylvieg Moderateurre : Nombres de Mersenne. 08-05-20 à 10:22

Bonjour,
Transforme 2n en y remplaçant \; n \; par \; p0q + r .
Regarde ce qui se passe modulo d.

Posté par Profil muriellesymre : Nombres de Mersenne. 08-05-20 à 10:49

Bonjour, merci pour votre réponse.

Donc on a 2^{p_0\times q+r} \equiv 1 [d] \iff 2^{p_0\times q} \times 2^r \equiv 1 [d]
Donc, si on veut que "ça marche", il faut que r = 0, ce qui revient à dire que p_0 | n
Est-ce que c'est vraiment rigoureux de le faire comme ça ?

Posté par Profil muriellesymre : Nombres de Mersenne. 08-05-20 à 10:55

Et donc pour finir la question, on peut dire que p_0 | p mais que p est premier donc p_0 = 1 ou  p_0 = p, mais  p_0 > 1 donc  p_0 = p  

Posté par
Sylvieg Moderateurre : Nombres de Mersenne. 08-05-20 à 10:58

Non, ça ne l'est pas.
Pourquoi faut-t-il r = 0 ?
Où utilises-tu les propriétés de p0 ?

Une remarque sur ton message précédent :
Logarithme et arithmétique font très rarement bon ménage.

Posté par Profil muriellesymre : Nombres de Mersenne. 08-05-20 à 11:07

Ah oui, vous avez raison.

On sait que 2^{p_0} \equiv 1 [d]
Donc (2^{p_0})^q \times 2^r \equiv 1^q \times 2^r [d]
Alors 2^r \equiv 1 [d]
Mais je ne vois pas comment conclure.

Posté par
Sylvieg Moderateurre : Nombres de Mersenne. 08-05-20 à 11:34

Définition de p0 ?

Posté par Profil muriellesymre : Nombres de Mersenne. 08-05-20 à 11:36

Plus petit élément de I, mais plus grand que 1

Posté par
Sylvieg Moderateurre : Nombres de Mersenne. 08-05-20 à 11:38

Oui.
L'entier r est-il dans I ?

Posté par Profil muriellesymre : Nombres de Mersenne. 08-05-20 à 11:39

Non, donc il y a une contradiction

Posté par Profil muriellesymre : Nombres de Mersenne. 08-05-20 à 11:46

Donc ça veut dire que n \neq p_0 \times q +r ?

Posté par
Sylvieg Moderateurre : Nombres de Mersenne. 08-05-20 à 12:14

Non, je te laisse chercher un peu.
Regarde bien la définition de l'ensemble I et ce que vérifie l'entier r.
Tu peux en déduire la valeur de r.

Posté par Profil muriellesymre : Nombres de Mersenne. 08-05-20 à 13:10

On a envie de dire que puisque 2^r \equiv 1[d], r \in I, et que comme I est l'ensemble des entiers naturels n non nuls de la forme 2^n \equiv 1[d], alors r est non nul, mais ce n'est pas ce qu'on veut montrer.

Posté par
Sylvieg Moderateurre : Nombres de Mersenne. 08-05-20 à 13:41

p0 est le plus petit entier naturel non nul de I.
Donc si un entier k vérifie 0 < k < p0 alors k n'est pas dans I.

A utiliser avec l'entier r.

Posté par Profil muriellesymre : Nombres de Mersenne. 08-05-20 à 14:18

Ah oui... eh bien c'est la définition de la division euclidienne dans ce cas là : 0 \le r < p_0

Posté par Profil muriellesymre : Nombres de Mersenne. 08-05-20 à 14:20

Donc r n'est pas dans I.

Donc  2^r \equiv 1[d] est faux

Posté par
Sylvieg Moderateurre : Nombres de Mersenne. 08-05-20 à 16:32

p0 est le plus petit entier naturel non nul de I.
Donc 2^r \equiv 1[d] est faux, sauf si \; r\; est égal à ....

Posté par
Sylvieg Moderateurre : Nombres de Mersenne. 08-05-20 à 16:37

Citation :
Soit I l'ensemble des entiers naturels n non nuls tels que 2^n \equiv 1[d]
Il y a donc 2 manières de ne pas être dans I :
1) Ne pas être un entier naturel non nul.
2) Ne pas vérifier 2^n \equiv 1[d]

Posté par Profil muriellesymre : Nombres de Mersenne. 08-05-20 à 17:06

Sylvieg @ 08-05-2020 à 16:32

p0 est le plus petit entier naturel non nul de I.
Donc  2^r \equiv 1[d] est faux, sauf si \; r\; est égal à ....

Si r = 0

Posté par Profil muriellesymre : Nombres de Mersenne. 08-05-20 à 17:08

Mais donc comme r n'est pas dans I, il y a bien une contradiction avec l'autre résultat non ?

Posté par
Sylvieg Moderateurre : Nombres de Mersenne. 08-05-20 à 17:51

Quel autre résultat ?

Posté par Profil muriellesymre : Nombres de Mersenne. 08-05-20 à 17:58

Rien, je me suis embrouillée avec autre chose.
Donc maintenant, il suffit de dire, que quand r = 0, p_0 | n ?

Posté par
Sylvieg Moderateurre : Nombres de Mersenne. 08-05-20 à 18:08

Il faut bien justifier que r=0.
Puis écrire n = p_0 \times q +r = p_0 \times q ; donc p0 divise n.
Je déteste la notation p|n

Reste à justifier p = p0.

Posté par Profil muriellesymre : Nombres de Mersenne. 08-05-20 à 18:13

D'accord, mais juste une chose : comment r peut-il être égal à 0 si p0 > 1  et que p0 est le plus petit élément de I ?

Posté par
Sylvieg Moderateurre : Nombres de Mersenne. 08-05-20 à 18:51

L'entier 0 n'est pas dans I et r non plus.

p0 est le plus petit élément de l'ensemble I.
Le seul entier naturel k qui vérifie à la fois k < p0 et 2k 1 [d] est 0.

C'est ce que vérifie r.

Posté par Profil muriellesymre : Nombres de Mersenne. 08-05-20 à 18:53

Ah oui d'accord

Posté par Profil muriellesymre : Nombres de Mersenne. 08-05-20 à 19:01

Donc la justification c'est :

comme 0 \le r < p_0, r n'est pas dans I donc il n'existe pas d'entier naturel non nul r tel que 2^r \equiv 1[d]. Donc la seule valeur possible de r pour valider ça est 0

Posté par Profil muriellesymre : Nombres de Mersenne. 08-05-20 à 19:03

et donc, comme p0 divise n, il divise aussi p \in I. Or p est premier, donc p0 = 1 ou p0 = p, mais p0>1, donc p0 = p

Posté par
Sylvieg Moderateurre : Nombres de Mersenne. 08-05-20 à 20:50

Citation :
il n'existe pas d'entier naturel non nul r tel que 2^r \equiv 1[d].
Je préfère : il n'existe pas d'entier naturel non nul n tel que \; 2^n \equiv 1[d]

Plus long, mais peut-être plus clair :
Un entier n est dans I si et seulement si il vérifie ces 2 conditions :
n est un entier naturel non nul (1)
2^n \equiv 1[d] \; (2)

r est un entier naturel.
Comme r < p_0 , r n'est pas dans l'ensemble I.
Mais l'entier naturel r vérifie (2)
Donc r ne vérifie pas (1)
Autrement dit, r n'est pas un naturel non nul.
Donc r = 0.
Donc r est nul.

Posté par
Sylvieg Moderateurre : Nombres de Mersenne. 08-05-20 à 21:00

muriellesym @ 08-05-2020 à 19:03

et donc, comme p0 divise n si n est dans I, il divise p \in I. Or p est premier, donc p0 = 1 ou p0 = p, mais p0>1, donc p0 = p

Posté par Profil muriellesymre : Nombres de Mersenne. 09-05-20 à 20:16

D'accord, merci pour votre précieuse aide. Il y a encore des questions que je n'ai pas renseignées dans mon premier message :

C. Etude de deux nombres de Mersenne

1. L'entier M_{19}=2^{19}-1=524287
D'après la question B3, les diviseurs premiers de M19 sont de la forme d=38k+1

  a. Combien y a-t-il de diviseurs de la forme  d=38k+1 , avec   d \le E(\sqrt{M_{19}} )   ?
  b. Démontrer que si K prend l'une des formes 3m+1, 5m+3,7m+2, avec m entier naturel, d n'est pas premier.
  c. Combien y a-t-il finalement de cas à examiner?M_{19} est-t-il premier?

2. L'entier M_{23} = 2^{23} - 1 = 8388607
Quel est le premier diviseur possible de M_{23} d'après B.3 ? M_{23} est t-il premier ?
----------------------------

Ma question est la suivante : que signifie le E() de E(\sqrt{M_{19}} )

Posté par
Sylvieg Moderateurre : Nombres de Mersenne. 09-05-20 à 20:55

Bonsoir,
E(x) désigne la partie entière de x.

Posté par Profil muriellesymre : Nombres de Mersenne. 10-05-20 à 13:44

Ah d'accord, merci

Posté par Profil muriellesymre : Nombres de Mersenne. 13-05-20 à 19:22

Bonjour, j'ai une autre question : dans la A.2, il faut déduire que (n composé) implique (M_n composé). Je ne vois pas vraiment comment faire, on ne peut pas factoriser à cause du + 1. Je ne trouve pas de liens entre les différents exemples.

Posté par
carpediemre : Nombres de Mersenne. 14-05-20 à 03:10

sz déduit immédiatement du 2a car 2^{pq} - 1 = (2^p)^q - 1 ...

Posté par Profil muriellesymre : Nombres de Mersenne. 14-05-20 à 08:58

2^{pq}-1 = (2^{pq-1}+2^{pq-2}+...+1)
Je ne vois pas comment on peut dire que (2^{pq-1}+2^{pq-2}+...+1) est composé

Posté par
Sylvieg Moderateurre : Nombres de Mersenne. 14-05-20 à 12:15

Bonjour,
Tu sembles avoir utilisé a^n-1 = (a-1)(a^{n-1}+a^{n-2}+...+1) avec a = 2 et n =pq

Tu n'as donc pas utilisé l'indication de carpediem :
2^{pq} - 1 = (2^p)^q - 1.
Applique \; a^n-1 = (a-1)(a^{n-1}+a^{n-2}+...+1) avec autre chose que a = 2 et n =pq.

Posté par Profil muriellesymre : Nombres de Mersenne. 14-05-20 à 13:14

a = 2^p et n = q ?

Posté par Profil muriellesymre : Nombres de Mersenne. 14-05-20 à 15:49

(2^p)^q-1 = ((2^p)^{q-1}+(2^p)^{q-2}+...+1)
mais ça ne règle pas le problème du +1

Posté par
Sylvieg Moderateurre : Nombres de Mersenne. 14-05-20 à 16:41

Ton égalité est fausse.
Tu y as oublié le facteur (a-1).

Posté par Profil muriellesymre : Nombres de Mersenne. 14-05-20 à 17:20

Ah oui effectivement, merci.

Sinon, j'ai un dernier problème : à la fin de la question B.3, il faut montrer que  d = 2kp+1.

J'ai montré que  p_0 divise d-1 donc d-1 = k \times p_0 = k \times p, k \in \mathbb{Z}
\iff d = kp +1, mais je ne vois pas d'où sort le "2" de d = {\color{red}2}kp +1

Posté par Profil muriellesymre : Nombres de Mersenne. 14-05-20 à 17:21

En fait, il faudrait que je montre que 2 divise d-1 mais je ne vois pas comment m'y prendre

Posté par
Sylvieg Moderateurre : Nombres de Mersenne. 14-05-20 à 18:02

Quand tu écris d-1 = kp, il faudrait utiliser une autre lettre que k.
d-1 = tp. Puis démontrer que t est pair, de la forme 2k.

L'entier d est impair puisqu'il divise 2p-1. Donc d-1 est pair.
L'entier p peut-il être pair ?

Il est premier ; donc n'est pair que si égal à 2.
Et là, il y a un os si p = 2 ; ce qui n'est pas exclu.
Pour moi, il y a une erreur d'énoncé.
Mais bon, je ne suis plus trop dedans.

Posté par Profil muriellesymre : Nombres de Mersenne. 14-05-20 à 18:12

Pourquoi si d-1 est pair, p l'est aussi ?

Posté par Profil muriellesymre : Nombres de Mersenne. 14-05-20 à 18:14

Peut être qu'on peut juste dire que comme d-1 et pair et que p divise d-1, alors il peut aussi être pair et donc forcément être égal à 2 comme il est premier.

1 2 +


Rechercher
Menu
Espace membre
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1681 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !