349. Démontrez que le nombre de Mersenne n°11 n’est pas premier et que le nombre de Mersenne n°13 est premier

Pour tout entier naturel $n\comma$ vous notez $M_n$ le nombre de Mersenne numéro $n\comma$ défini par la formule suivante :

M_n = 2^n-1.

Dans ce contenu, 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}\comma$ notés $d$ et $d’\comma$ 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’ \gt (\sqrt{2047})^2$ donc $dd’ \gt 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\comma$ est divisible par un nombre premier $p$ qui lui est inférieur ou égal, de sorte que $p\leq \sqrt{2047}.$ Ce nombre premier $p$ divise donc $2047.$

Comme $40^2 =1600$ et comme $50^2=2500\comma$ vous calculez $45^2 =2025.$ Puis $46^2 =45^2 + 45+46 =2025+45+46 =2070+46 =2116.$ Ces résultats prouvent que $45\lt\sqrt{2047}\lt46.$ Comme $p\leq \sqrt{2047} \lt 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\comma$ il s’ensuit que :

2^{11}\equiv 1\mod p.

Cette écriture montre que $2$ est inversible modulo $p\comma$ et que $2^{10}$ en est un inverse modulo $p.$ En particulier $p\neq 2.$

Notez $r$ l’ordre de $2$ modulo $p.$ Comme $2^{11} \equiv 1 \mod p\comma$ vous avez $r\mid 11.$ Or, $11$ est un nombre premier, donc $r = 1$ ou $r=11.$

Si $r=1\comma$ alors $2\equiv 1 \mod p$ donc $1\equiv 0 \mod p$ donc $p\mid 1$ ce qui est absurde.

Donc $r=11.$

Comme $p$ est un nombre premier qui ne divise pas $2\comma$ le petit théorème de Fermat fournit $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}\comma$ notés $d$ et $d’\comma$ 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’ \gt (\sqrt{8191})^2$ donc $dd’ \gt 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\comma$ est divisible par un nombre premier $p$ qui lui est inférieur ou égal, de sorte que $p\leq \sqrt{8191}.$ Ce nombre premier $p$ divise donc $8191.$

Comme $90^2 =8100$ et comme $91^2=90^2+90+91 =8100+181=8281\comma$ vous avez $90\lt\sqrt{8191}\lt91.$ Comme $p\leq \sqrt{8191} \lt 91$ vous déduisez que $\boxed{p\leq 90.}$

Comme $8191 = 2^{13}-1$ et comme $p\mid 2^{13}-1\comma$ il s’ensuit que :

2^{13}\equiv 1\mod p.

Cette écriture montre que $2$ est inversible modulo $p\comma$ et que $2^{12}$ en est un inverse modulo $p.$ En particulier $p\neq 2.$

Notez $r$ l’ordre de $2$ modulo $p.$ Comme $2^{13} \equiv 1 \mod p\comma$ vous avez $r\mid 13.$ Or, $13$ est un nombre premier, donc $r = 1$ ou $r=13.$

Si $r=1\comma$ alors $2\equiv 1 \mod p$ donc $1\equiv 0 \mod p$ donc $p\mid 1$ ce qui est absurde.

Donc $r=13.$

Comme $p$ est un nombre premier qui ne divise pas $2\comma$ le petit théorème de Fermat fournit $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\comma$ $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, $53\times 154 = 8162$ et $53\times 155 = 8215\comma$ donc $154\lt\frac{8191}{53}\lt155.$ De même, $79\times 103 = 8137$ et $79\times 104 = 8216\comma$ donc $103\lt\frac{8191}{79}\lt104.$ Ces deux quotients ne sont pas entiers.

Par contraposée, comme $8191$ n’est divisible ni par $53\comma$ ni par $79\comma$ il est premier.

Concluez

\boxed{M_{13} \text{ est un nombre premier.}}