Forum de mathématiques - Bibm@th.net

Vani94

Membre

Inscription : 04-11-2022

Messages : 26

Nombre de mersenne

Bonjour,  j'ai quelques difficultés répondre à ces questions, pourriez-vous m'aider s'il-vous-plaît ? Voici l'énoncé :

On appelle nombres de mersenne, les nombres $Mn$ de la forme $Mn=2^n-1$ avec $n$ appartenant à $N^*$.

1)Soit $n$ appartenant à $N^*$ et $a$ un entier.
a) Démontrer que $a-1$ divise $a^n-1$.
b)En déduire que, si $d$ divise $n$ alors $2^d-1$ divise $Mn$

2) Démontrer que si $Mn$ est premier alors $n$ est premier. La réciproque est-elle vraie ?

3)Soient $a$ et $n$ deux entier tels que : $a》2$ et $n》2$. Démontrer que si $a^n-1$ est premier alors $a=2$ et $n$ est premier.

4) Soit $n$ un nombre premier impair et soit $p$ un diviseur premier de $Mn$. On considère l'ensemble $E$ des nombres entiers $s$ tels que $2^s$ congru à $1 [p]$.Soit $s0$ le plus petit élément de $E$.

a) Soit $s$  un élément de l'ensemble $E$.Démontrer que $s$ est un multiple de $s0$ (Indication : faire la division euclidienne de $s$ par $s0$).

b)En déduire que $s0$ divise $n$ puis que $s0=n$.

c) On rappelle le petit théorème de Fermat:
$《$Soit $p$ un nombre premier et à un entier naturel. Si $p$ ne divise pas $a$, alors $a^p-1$ congru $1[p]》$
Démontrer que $n$ divise $p-1$ et $2n$ divise $p-1$.

d) En déduire que $p$ s'écrit sous la forme $p=2kn+1$ avec $k$ appartenant $N$.
e) Application : Trouver un diviseur premier de $M23$.

Et quelques éléments de réponses :

1)b. $d$ divise $n$ donc $d$ divise $2^n-1$ donc $d$ divise $Mn$ or $d$ divise $2^d-1$ donc $2^d-1$ divise $n$

2)Si n est premier , $Mn$ n'est pas forcément premier : ex pour $n=11$, $M11= 2047$ qui n'est pas un nombre premier puisqu'il est divisible par $23$ et $89$.

3) Pour que $a^n-1$ soit premier, il faut qu'il est exactement $2$ diviseurs , 1 et lui-même. Si $a^n-1=1$ alors $a^n =2$

4)a. $s$ est un multiple de $s0$ si il existe un entier $t$ tel que $s0×t=s$ donc $s÷s0 =$...

4)b. $s0$ divise $s$ et $s$  divise $2^s-1$ or $2^s-1$ congru à $0 [p ]$ donc $p$ divise 2^s-1 sachant que $p$ est un diviseur premier de $Mn$  et donc $p$ divise $n$ alors $s0$ divise $n$.
Pour la suite : Démontrer que $n$ divise $s0$ car si $s0$ divise $n$ et si $n$ divise $s0$ alors $s0=n$

e)$M23=2^{23}-1=8388607$ qui est un nombre parfait , un diviseur de $M23$est donc $8388607$ ou $1$.

Dernière modification par Vani94 (08-05-2023 08:43:33)

Glozi

Invité

Re : Nombre de mersenne

Bonjour,
Il y a beaucoup de non sens et de confusions sur la divisibilité, et les nombres premiers.

Pour la question 1)a) c'est un classique à connaitre, on peut trouver la réponse en calculant $\sum_{k=0}^{n-1}a^k$.

Pour la 1)b) "$d | n$ donc $d |2^n-1$", d'où ça sort ? (d'ailleurs c'est complètement faux, prendre $d=n=2$).
Ensuite "$d | 2^d-1$ et $d |2^n-1$ donc $2^d-1 | 2^n-1$". Il n'y a rien qui va ici, "$d|2^d-1$" est faux encore une fois (tester sur $d=2$, $d=3$ etc...), et l'implication "$a|b$ et $a|c$ donc $b|c$" est complètement fausse également.
Je t'invite à reprendre sérieusement cette question, il faut juste appliquer la question précédente pour un bon choix de $a$ et un bon choix de $n$.

Pour la 2) tu as bien trouvé un contre exemple à la réciproque. Pour montrer $M_n$ premier implique $n$ premier, il suffit d'appliquer judicieusement la question 1)b) (que se passe-t-il si $n$ n'est pas premier).

Pour la 3) ta première phrase est correcte, je ne vois pas ce que tu cherches à dire avec la seconde...
Procède par étape, suppose $a^n-1$ premier, d'abord montre que $a=2$ puis montre que $n$ premier. Il s'agit juste d'appliquer les questions précédentes.

Pour la 4) je pense que $E$ est plutôt l'ensemble des entiers $s$ strictement positifs tels que $2^s \equiv 1 [p]$. (avant de prendre $s_0$ le minimum de $E$, il serait bon de dire pourquoi $E\subset \mathbb{N}$ est non vide).
J'ai lu en diagonale, mais j'ai l'impression que tu répètes encore le même type d'erreur qu'avant, je te laisse donc réessayer.

Au niveau de la rédaction, essaye de dire clairement quelles sont les questions précédentes que tu appliques et avec quels paramètres, ça t’évitera à toi aussi des erreurs.

PS : si tu n'es pas familier avec cette écriture $a|b$ se lit "$a$ divise $b$" et signifie $\exists k\in \mathbb{Z}, b=ak$.

Bonne journée

Vani94

Membre

Inscription : 04-11-2022

Messages : 26

Re : Nombre de mersenne

Bonjour,

En prenant compte de vos indications et autres, j'ai pu faire ceci pour l'instant :

1)a. $\sum_{k=0}^{n-1} a^n\,=\,1+a+a^2+...+a^{n-1}=\frac{1-a^n}{1-a}$

2) Mn est composé si n n'est pas premier

3) Si $a^n-1$ est premier alors $a$ différent de $0$ et $1$ puisque $0$ et $1$ ne sont pas premier. D'après la question 1)a. : $a^n-1 = (a-1)(a^n-1+...+a^2+a+1)$, l'un des deux facteurs est donc égal à $1$ or $(a^n-1+...+a^2+a+1) > 1$ donc $(a-1)=1 \longleftrightarrow a=2$

Par contre pour la 1)b je ne comprends toujours pas comment procéder, à part si $n=d$ et $a = 2$

Dernière modification par Vani94 (08-05-2023 15:08:15)

Glozi

Invité

Re : Nombre de mersenne

Rebonjour,
1)a) oui la relation est correcte (sauf pour $a=1$), il faudrait conclure à pourquoi cela implique $a-1 | a^n -1$.
2) Oui mais pourquoi ?
3) Pour ta première phrase, remarque qu'on suppose dans l'énoncé que $a\geq 2$. Ensuite tu as bien trouvé $a^n-1$ premier implique que $a=2$ il reste à justifier que $n$ doit alors aussi être premier.

Pour la 1)b), tu sais par 1)a) que $\forall a\geq 1, \forall m\geq 1, a-1 | a^m -1$.
Il suffit de trouver $a$ et $m$ en fonction de $n$ et $d$ de sorte que la conclusion soit celle que tu veux. $2^d-1 | 2^n -1$.

Vani94

Membre

Inscription : 04-11-2022

Messages : 26

Re : Nombre de mersenne

3) Prenons $n$ composé tel que $n=t×r$ on a : $a^n-1= 2^{tr}-1 = (2^t-1)(2^{r-1}+...+2^{2r}+2^r+1)$ si $2^{tr}-1$ est premier alors l'un des facteurs est égal à $1$ or $(2^t-1) > 1$ et $(2^{r-1}+...+2^{2r}+2^r+1) >1$ donc $n$ est forcément premier.

1)b. si je reprends votre propriété sur la divisibilité :
Si $d\mid{n}$ alors $\exists k \in \mathbb{Z}$ tel que $n = kd$ et $2^d-1\mid2^{dk}-1$ ainsi $\frac{1-{(2^d)}^k}{1-(2^d)}$ donc $2^d-1$ divise $2^n-1$ et donc $Mn$

4)a. Division euclidienne : $a=bq+r$, si $s$ est un multiple de $s0$ alors $s =s0q+r$ avec $0\leq r < s0$
$2^s-1 \equiv 0 [p]  \leftrightarrow2^{s0q+r}  \equiv 1 [p] \leftrightarrow{(2^{s0})}^q × 2^r  \equiv 1 [p] $

Dernière modification par Vani94 (08-05-2023 21:22:09)

Glozi

Invité

Re : Nombre de mersenne

Bonjour,
Ta factorisation dans 3) est fausse, mais l'idée est là. Il est maladroit (d'autant plus si on se trompe) de refaire une factorisation explicite alors qu'on a déjà la question 1)a) à disposition.
1)b) ta rédaction n'est pas claire du tout, je pense que l'idée est là mais je ne suis pas devin. Le plus clair encore une fois est d'appliquer la question 1)a) avec le bon $a$ et le bon $n$.
4)a) C'est très confus, il y a des mots et des idées mais tout dans le désordre. Par exemple "si $s$ est un multiple de $s_0$ alors $s=s_0q+r$ avec $0\leq r <s_0$" n'est pas faux mais n'est pas du tout ce qu'on veut ! Pour écrire la division euclidienne de $s$ par $s_0$ il n'y a pas besoin de supposer que $s_0$ divise $s$ (bien au contraire). En revanche, une fois qu'on a écrit la division euclidienne, ce qu'on peut dire c'est que $s$ est un multiple de $s_0$ si et seulement si le reste est nul.

Bonne journée