Bonjour à tous!
On se propose d'étudier les nombres de Mersennes M(n)=2^n-1 où n est un entier >=2.
1) calculer M(11) puis montrer qu'il n'est pas premier
2) vérifier que M(13) est premier
Pour 1) M(11)=2^11-1=2047 et en cherchant à décomposer j'ai trouvé 2047=23*89 mais c'est long... y a t-il une méthode rapide?
Pour 2) M(13)=2^13-1=8192-1=8091 mais je n'ai pas réussi à démontrer qu'il est premier... Quelle est la technique?
Nombre de Mersenne
Re: Nombre de Mersenne
Bonjour
Soit $p$ premier et on considère les nombres $M_p$
Supposons que $M_p$ admette un diviseur premier $d$ (nécessairement impair). Soit $I=\{n\in {\mathbb N}\ \ 2^n\equiv 1\ [d]\}$
$I$ n'est pas vide et admet un plus petit élément $p_0>1$
On considère la division euclidienne de $n\in I$ par $p_0$ : $n=kp_0+r\equiv 1\ [d]$ et $r<p_0$
$2^{kp_0+r}\equiv 1\ [d]$. $(2^{p_0})^k\equiv 1\ [d]$ donc $2^r\equiv 1\ [d]$. Donc $r\in I$ et $r<p_0$ implique $r=0$
Tout élément de $I$ est donc multiple de $p_0$.
Or $2^p\equiv 1\ [d]$ et $p$ est premier donc $p_0=p$
Par le petit théorème de Fermat, $2^{d-1}\equiv 1\ [d]$ donc $d-1$ est multiple de $p$.
On en déduit que tout diviseur premier $d$ de $M_p$ est de la forme $2kp+1$ et $d\leq E(\sqrt{2^p-1})$
Avec $p=11$, $d=22k+1$ et $d\leq 45$. Il y avait donc un seul essai à faire avec $d=23$.
Avec $p=13$, $d=26 k +1$ et $d\leq 89$. Donc 2 essais à faire avec $d=53$ et $d=79$.
Soit $p$ premier et on considère les nombres $M_p$
Supposons que $M_p$ admette un diviseur premier $d$ (nécessairement impair). Soit $I=\{n\in {\mathbb N}\ \ 2^n\equiv 1\ [d]\}$
$I$ n'est pas vide et admet un plus petit élément $p_0>1$
On considère la division euclidienne de $n\in I$ par $p_0$ : $n=kp_0+r\equiv 1\ [d]$ et $r<p_0$
$2^{kp_0+r}\equiv 1\ [d]$. $(2^{p_0})^k\equiv 1\ [d]$ donc $2^r\equiv 1\ [d]$. Donc $r\in I$ et $r<p_0$ implique $r=0$
Tout élément de $I$ est donc multiple de $p_0$.
Or $2^p\equiv 1\ [d]$ et $p$ est premier donc $p_0=p$
Par le petit théorème de Fermat, $2^{d-1}\equiv 1\ [d]$ donc $d-1$ est multiple de $p$.
On en déduit que tout diviseur premier $d$ de $M_p$ est de la forme $2kp+1$ et $d\leq E(\sqrt{2^p-1})$
Avec $p=11$, $d=22k+1$ et $d\leq 45$. Il y avait donc un seul essai à faire avec $d=23$.
Avec $p=13$, $d=26 k +1$ et $d\leq 89$. Donc 2 essais à faire avec $d=53$ et $d=79$.