Pour tout entier naturel $n$, vous notez $M_n$ le nombre de Mersenne numéro $n$, défini par la formule suivante :
M_n = 2^n-1.
Dans cet article, vous cherchez à déterminer des diviseurs premiers candidats des nombres $M_{11}$ et $M_{13}$ afin d’éviter des tests successifs de divisibilité qui peuvent rapidement devenir longs.
Étudiez le nombre de Mersenne n°11
Analyse
Par définition :
\begin{align*}
M_{11} &= 2^{11}-1\\
&= 2^4 2^4 2^3-1\\
&=16\times 16\times 8 -1\\
&=256\times 8 -1\\
&=2048 - 1\\
&=2047.
\end{align*} Supposez que $M_{11}$ ne soit pas un nombre premier. Alors il existe deux diviseurs propres de $M_{11}$, notés $d$ et $d’$, tels que $2\leq d\leq 2046$ puis $2\leq d’\leq 2046$ et $2047 = dd’.$
Si $d$ et $d’$ sont tous les deux strictement supérieurs à $\sqrt{2047}$ il s’ensuit que $dd’ > (\sqrt{2047})^2$ donc $dd’ > 2047$ ce qui est absurde.
Donc $2047$ admet un diviseur propre inférieur ou égal à $\sqrt{2047}.$ Par suite, ce diviseur propre, supérieur ou égal à $2$ est divisible par un nombre premier $p.$ Ce nombre premier $p$ divise donc $2047.$
Comme $40^2 =1600$ et comme $50^2=2500$, vous calculez $45^2 =2025.$ Puis $46^2 =45^2 + 45+46 =2025+45+46 =2070+46 =2116.$ Ces résultats prouvent que $45<\sqrt{2047}<46.$ Comme $p\leq \sqrt{2047} < 46$ vous déduisez que $\boxed{p\leq 45.}$
Il serait possible de tester tous les nombres premiers inférieurs ou égaux à $45$ mais il y en a encore trop.
Un argument de théorie des groupes va permettre de limiter grandement les possibilités.
Comme $2047 = 2^{11}-1$ et comme $p\mid 2^{11}-1$, il s’ensuit que :
2^{11}\equiv 1\mod p.Cette écriture montre que $2$ est inversible modulo $p$ (et que $2^{10}$ est son inverse modulo $p.$)
Notez $r$ l’ordre de $2$ modulo $p.$ Comme $2^{11} \equiv 1 \mod p$, vous avez $r\mid 11.$ Or, $11$ est un nombre premier, donc $r = 1$ ou $r=11.$
Si $r=1$, alors $2\equiv 1 \mod p$ donc $1\equiv 0 \mod p$ donc $p\mid 1$ ce qui est absurde.
Donc $r=11.$
D’après le petit théorème de Fermat, $2^{p-1}\equiv 1 \mod p$ donc $r\mid p-1$ ce qui s’écrit : $p\equiv 1 \mod 11.$
Vous en déduisez que :
p\in\{1, 12, 23, 34, 45\}.De cette liste, vous excluez $1$ qui n’est pas premier car strictement inférieur à $2$. Vous excluez $12$ et $34$ qui sont pairs et divisibles par $2$ donc non premiers. Vous excluez aussi $45$ qui est divisible par $5.$
Vous en déduisez que $\boxed{p=23.}$
Synthèse
D’après ce qui précède, si $2047$ n’est pas un nombre premier, il est divisible par $23.$
En effectuant la division, vous constatez que $\frac{2047}{23} = 89.$
Concluez
Ainsi, $2047 = 23\times 89.$
\boxed{M_{11} \text{ n'est pas un nombre premier.}}Étudiez le nombre de Mersenne n°13
Analyse
Par définition :
\begin{align*}
M_{13} &= 2^{13}-1\\
&= 2^{11} \times 4-1\\
&=2048\times 4 -1\\
&=8192 -1\\
&=8191.
\end{align*} Supposez que $M_{13}$ ne soit pas un nombre premier. Alors il existe deux diviseurs propres de $M_{13}$, notés $d$ et $d’$, tels que $2\leq d\leq 8190$ puis $2\leq d’\leq 8190$ et $8191 = dd’.$
Si $d$ et $d’$ sont tous les deux strictement supérieurs à $\sqrt{8191}$ il s’ensuit que $dd’ > (\sqrt{8191})^2$ donc $dd’ > 8191$ ce qui est absurde.
Donc $8191$ admet un diviseur propre inférieur ou égal à $\sqrt{8191}.$ Par suite, ce diviseur propre, supérieur ou égal à $2$ est divisible par un nombre premier $p.$ Ce nombre premier $p$ divise donc $8191.$
Comme $90^2 =8100$ et comme $91^2=90^2+90+91 =8100+181=8281$, vous avez $90<\sqrt{8191}<91.$ Comme $p\leq \sqrt{8191} < 91$ vous déduisez que $\boxed{p\leq 90.}$
Comme $8191 = 2^{13}-1$ et comme $p\mid 2^{13}-1$, il s’ensuit que :
2^{13}\equiv 1\mod p.Cette écriture montre que $2$ est inversible modulo $p$ (et que $2^{12}$ est son inverse modulo $p.$)
Notez $r$ l’ordre de $2$ modulo $p.$ Comme $2^{13} \equiv 1 \mod p$, vous avez $r\mid 13.$ Or, $13$ est un nombre premier, donc $r = 1$ ou $r=13.$
Si $r=1$, alors $2\equiv 1 \mod p$ donc $1\equiv 0 \mod p$ donc $p\mid 1$ ce qui est absurde.
Donc $r=13.$
D’après le petit théorème de Fermat, $2^{p-1}\equiv 1 \mod p$ donc $r\mid p-1$ ce qui s’écrit : $p\equiv 1 \mod 13.$
Vous en déduisez que :
p\in\{1, 14, 27, 40, 53, 66, 79\}.De cette liste, vous excluez $1$ qui n’est pas premier car strictement inférieur à $2$. Vous excluez $14$, $40$ et $66$ qui sont pairs et divisibles par $2$ donc non premiers. Vous excluez aussi $27$ qui est divisible par $3.$
Du coup :
\boxed{p\in\{ 53, 79\}.}Synthèse
D’après ce qui précède, si $M_{13} = 8191$ n’est pas un nombre premier, il est divisible par $53$ ou par $79.$
Or, les divisions montrent que $154<\frac{8191}{53}<155$ et que $103<\frac{8191}{79}<104.$
Par contraposée, comme $8191$ n’est divisible ni par $53$, ni par $79$, il est premier.
Concluez
\boxed{M_{13} \text{ est un nombre premier.}}Partagez !
Diffusez cet article auprès de vos connaissances susceptibles d'être concernées en utilisant les boutons de partage ci-dessous.
Aidez-moi sur Facebook !
Vous appréciez cet article et souhaitez témoigner du temps que j'y ai passé pour le mettre en œuvre. C'est rapide à faire pour vous et c'est important pour moi, déposez un j'aime sur ma page Facebook. Je vous en remercie par avance.
Lisez d'autres articles !
Parcourez tous les articles qui ont été rédigés. Vous en trouverez sûrement un qui vous plaira !