Il s’agit d’un test de calcul modulaire qui permet de démontrer, sans effectuer de divisions successives, qu’un nombre donné n’est pas premier.
Démontrez un lemme
Pour tout entier naturel $n$ supérieur ou égal à $2$ vous notez $\mathscr{P}(n)$ la propriété « il existe un entier naturel $t$ et un entier naturel impair $q$ tels que $n = 2^t q$ ».
Initialisation. Pour $n=2$, vous posez $t = 1$ et $q=1.$ Vous avez bien $2^t q = 2^1 \times 1 = 2 = n.$ Donc $\mathscr{P}(2)$ est vraie.
Hérédité. Soit $n$ un entier supérieur ou égal à $2.$ Supposez que $\mathscr{P}(2),\dots, \mathscr{P}(n)$ sont vraies.
Notez déjà que $n+1\geq 3.$ Si $n+1$ est impair, alors vous posez $t = 0$ et $q = n+1.$ Vous avez immédiatement $2^t q = 2^0 \times (n+1) = n+1.$
Si $n+1$ est pair, il s’ensuit que $n+1\geq 4.$ Alors $m = \frac{n+1}{2}$ est un entier supérieur ou égal à $2.$
Comme $n\geq 1$ il vient $2n \geq n+1$ et donc $\frac{n+1}{2}\leq n.$
Comme $m\in\llbracket 2, n\rrbracket$ vous appliquez l’hypothèse de récurrence. Il existe un entier naturel $t’$ et un entier naturel impair $q$ tels que $m = 2^{t’} q.$ Du coup $2m = 2^{1+t’}q$ ce qui s’écrit $n+1 = 2^{1+t’} q.$ En posant $t = 1+t’$ vous constatez que $t\in\N$ et vous avez bien $n+1 = 2^t q.$
Donc $\mathscr{P}(n+1)$ est vraie.
Conclusion. Par récurrence forte, il a été démontré que :
\boxed{\forall n\in\N, n\geq 2\implies (\exists t \in\N, \exists q\in\N, n = 2^tq\text{ et }q\text{ est impair}).}Soient $t, q, u, r$ quatre entiers naturels avec $2^t q = 2^u r$ et $q$ et $r$ impairs.
Si $t> u$ alors $t\geq u+1.$ Vous avez $2^{t-u} q = r.$ Or, $t-u \geq 1$ donc $2^{t-u}q$ est pair. Or $r$ est impair, contradiction.
Si $u> t$ alors $u\geq t+1.$ Vous avez $q = 2^{u-t} r.$ Or, $u-t \geq 1$ donc $2^{u-t}r$ est pair. Or $q$ est impair, contradiction.
Du coup, $u=t.$ Ainsi $2^t q = 2^t r$ et $q=r.$
En définitive l’unicité est démontrée.
\boxed{\forall n\in\N, n\geq 2\implies (\exists! t \in\N, \exists !q\in\N, n = 2^tq\text{ et }q\text{ est impair}).}Descriptif du test de Miller en base $b$
Soit $b$ un nombre entier supérieur ou égal à $2$ appelé base.
Soit $n$ un entier naturel impair. D’après le lemme, il existe un unique entier naturel $t$ et un unique entier naturel impair $q$ tels que $n-1 = 2^t q.$ Notez que $t=0$ entraîne $n-1 =q$ et $n-1$ serait impair donc $n$ serait pair ce qui est absurde, donc $t \geq 1.$
Vous direz que $n$ passe le test de Miller en base $b$, si et seulement si :
\boxed{(b^q\equiv 1 \mod n) \text{ ou } (\exists s\in\llbracket 0, t-1\rrbracket, b^{2^s q}\equiv -1 \mod n).}Note. Un nombre entier supérieur ou égal à $2$ qui passe le test de Miller en base $b$ peut ne pas être premier. Dans ce dernier cas précis, il est qualifié de nombre pseudo-premier fort en base $b.$
L’intérêt du test de Miller réside dans le théorème ci-dessous.
Tout nombre premier $p$ impair passe le test de Miller en base $b$ dès que $b$ n’est pas multiple de $p$
Soit $b$ un nombre entier supérieur ou égal à $2$ appelé base.
Soit $p$ un nombre premier impair tel que $b$ ne soit pas un multiple de $p.$
Comme $p-1$ est pair, il existe un unique entier naturel $t$ et un unique entier impair $q$ tels que $p-1 = 2^t q.$
S’il existe $s\in\llbracket 0, t-1\rrbracket, b^{2^s q}\equiv -1 \mod p$ alors $p$ passe le test de Miller en base $b.$
Si un tel entier $s$ n’existe pas, cela signifie ce qui suit :
\forall s\in\llbracket 0, t-1\rrbracket, b^{2^sq}\not\equiv -1 \mod p.Pour tout entier naturel $u$ vous notez $\mathscr{P}(u)$ la propriété « $b^{2^u q} \equiv 1 \mod p$. » Vous procédez par récurrence descendante.
Initialisation. Pour $u = t$ vous cherchez à évaluer $b^{2^uq} = b^{2^tq} = b^{p-1}.$ Comme $PGCD(b,p)$ divise $p$, ce nombre vaut $1$ ou $p$ car $p$ est premier. Si $PGCD(b,p)=p$ alors $p$ divise $b$ ce qui est absurde. Donc $PGCD(b,p)=1.$ L’application du petit théorème de Fermat fournit $b^{p-1} \equiv 1\mod p$ ce qui prouve que $\mathscr{P}(t)$ est vraie.
Caractère descendant. Soit $u$ un nombre entier appartenant à l’intervalle $\llbracket 1, t \rrbracket.$ Supposez $\mathscr{P}(u)$ vraie.
Alors $b^{2^u q} \equiv 1 \mod p.$ Vous en déduisez que :
\begin{align*}
\left(b^{2^{u-1} q}\right)^2 \equiv 1 \mod p\\
\left(b^{2^{u-1} q}\right)^2 -1^2 \equiv 0 \mod p\\
\left(b^{2^{u-1} q}-1\right)\left(b^{2^{u-1} q}+1\right) \equiv 0 \mod p.
\end{align*}Donc $p$ divise le produit $\left(b^{2^{u-1} q}-1\right)\left(b^{2^{u-1} q}+1\right).$
Cependant, notez que $u-1\in\llbracket 0, t-1\rrbracket$ donc $b^{2^{u-1}q}\not\equiv -1 \mod p$ donc $p$ ne divise pas $b^{2^{u-1} q}+1.$
Utilisant le lemme d’Euclide, vous déduisez que $p$ divise $b^{2^{u-1} q}-1$ et donc $b^{2^{u-1} q}\equiv 1 \mod p.$
La propriété $\mathscr{P}(u-1)$ est vraie.
Conclusion. Il a été démontré par récurrence descendante que $\mathscr{P}(0)$ est vraie, autrement dit $b^{2^0 q} \equiv 1 \mod n$ ce qui fournit $b^{ q} \equiv 1 \mod p.$
Ainsi $p$ passe le test de Miller en base $b.$
Application : démontrez que $1387$ n’est pas un nombre premier
Tout nombre premier $p$ passe le test de Miller en base $b$ dès que $PGCD(b,p)=1.$
Par contraposée, si $n$ est un nombre entier supérieur ou égal à $2$ de sorte que :
- il existe une base $b$ vérifiant $PGCD(b,n)=1$
- le nombre $n$ ne passe pas le test de Miller en base $b$
alors $n$ n’est pas premier.
Note. En pratique la base $b$ est choisie pour être strictement inférieure à $n$. S’il s’avère que $PGCD(b,n)\geq 2$ alors ce nombre est déjà un diviseur de $n$ compris entre $2$ et $n-1.$ Il est inutile de pratiquer le test de Miller puisque $n$ est déjà non premier.
Pour le nombre $n = 1387$ vous choisissez $b=2$ pour base. Comme $1387$ est impair, $PGCD(n,b)=1.$ Vous appliquez le test de Miller à $1387$ en base $2.$
Tout d’abord :
\begin{align*}
n-1 &= 1386\\
&= 2\times 693.
\end{align*} Par conséquent $t = 1$ et $q = 693.$
Vous évaluez $2^{693} \mod 1387.$
D’une part :
\begin{align*}
2^{10}&\equiv 1024 \mod 1387\\
2^{20}&\equiv 1024^2 \mod 1387\\
2^{20}&\equiv 1048576 \mod 1387\\
2^{20}&\equiv 756\times 1387+ 4 \mod 1387\\
2^{20}&\equiv 2^2 \mod 1387.
\end{align*} Comme $PGCD(2, 1387)=1$ vous pouvez simplifier la congruence deux fois par $2$ grâce au théorème de Gauss, ce qui fournit :
\boxed{2^{18}\equiv 1\mod 1387.}D’autre part, vous effectuez la division euclidienne de $693$ par $18$ ce qui fournit :
693 = 18\times 38 + 9.
Du coup :
\begin{align*}
2^{693} &\equiv 2^9 \times (2^{18})^{38} \mod 1387\\
&\equiv 512\mod 1387.
\end{align*} Comme $2^{693}$ n’est ni congru à $1$ ni congru à $-1$ modulo $1387$, $1387$ ne passe pas le test de Miller en base $2$ donc $1387$ n’est pas premier.
Application : démontrez que le nombre $1\,373\,653$ n’est pas premier
Il s’agit de déterminer $t$ et $q.$
Vous notez $n = 1373653$ et par suite :
\begin{align*}
n-1 &= 1\,373\,652 \\
&= 2\times 686\,826\\
&= 4\times 343\,413.
\end{align*}Vous choisissez $b=5$ pour base et allez effectuer le calcul de $5^{343\,413}$ modulo $1\,373\,653.$ Pour plus de lisibilité, les congruences qui suivent sont toutes effectuées modulo $1\,373\,653.$
\begin{align*}
5^2 &= 25\\
5^4 &= 25^2 =625 \\
5^8 &= 625^2 = 360\,425+024\,200+006\,000 = 360\,425+30\,200 =390\,625\\
5^{16} &\equiv 390\,625^2 \equiv 152\,587\,890\,625 \equiv 1\,373\,653\times 111\,081 + 1\,141\,732\\
5^{16} &\equiv 1\,141\,732\\
5^{32} &\equiv 1\,141\,732^2 \equiv 1\,303\,551\,959\,824 \equiv 948\,967\times 1\,373\,653+593\,373\\
5^{32} &\equiv 593\,373\\
5^{64} &\equiv 593\,373^2 \equiv 352\,091\,517\,129 \equiv 256\,317\times 1\,373\,653+901\,128\\
5^{64} &\equiv 901\,128\\
5^{128} &\equiv 901\,128^2 \equiv 812\,031\,672\,384 \equiv 591\,147\times 1\,373\,653+822\,393\\
5^{128} &\equiv 822\,393
\end{align*}\begin{align*}
5^{256} &\equiv 822\,393^2 \equiv 676\,330\,246\,449 \equiv 492\, 358\times 1\,373\,653 + 1\,202\,675\\
5^{256} &\equiv 1\,202\,675\\
5^{512} &\equiv 1\,202\,675^2 \equiv 1\,446\,427\,155\,625 \equiv 1\,052\,978\times 1\,373\,653+ 766\,991\\
5^{512} &\equiv 766\,991\\
5^{1024} &\equiv 766\,991^2 \equiv 588\,275\,194\,081 \equiv 428\,256\times 1\,373\,653+ 54\,913\\
5^{1024} &\equiv 54\,913\\
5^{2048} &\equiv 54\,913^2 \equiv 3\,015\,437\,569 \equiv 2\,195\times 1\,373\,653+ 269\,234\\
5^{2048} &\equiv 269\,234\\
5^{4096} &\equiv 269\,234^2 \equiv 72\,486\,946\,756 \equiv 52\,769\times 1\,373\,653+ 651\,599\\
5^{4096} &\equiv 651\,599
\end{align*}\begin{align*}
5^{8192} &\equiv 651\,599^2 \equiv 424\,581\,256\,801 \equiv 309\,089\times 1\,373\,653 + 224\,684\\
5^{8192} &\equiv 224\,684\\
5^{16384} &\equiv 224\,684^2 \equiv 50\,482\,899\,856 \equiv 36\,750\times 1\,373\,653 + 1\,152\,106\\
5^{16384} &\equiv 1\,152\,106\\
5^{32768} &\equiv 1\,152\,106^2 \equiv 1\,327\,348\,235\,236 \equiv 966\,290\times 1\,373\,653 + 1\,077\,866\\
5^{32768} &\equiv 1\,077\,866\\
5^{65536} &\equiv 1\,077\,866^2 \equiv 1\,161\,795\,113\,956 \equiv 845\,770\times 1\,373\,653 + 616\,146\\
5^{65536} &\equiv 616\,146\\
5^{131072} &\equiv 616\,146^2 \equiv 379\,635\,893\,316 \equiv 276\,369\times 1\,373\,653 + 787\,359\\
5^{131072} &\equiv 787\,359\\
\end{align*}\begin{align*}
5^{262144} &\equiv 787\,359^2 \equiv 619\,934\,194\,881 \equiv 451\,303\times 1\,373\,653 + 475\,022\\
5^{262144} &\equiv 475\,022.
\end{align*}Vous décomposez $343\,413$ comme une somme de puissances de $2$ à l’aide de soustractions.
\begin{align*}
343\,413 -262\,144 &= 81\,269\\
81\,269 - 65\,536&=15\,733\\
15\,733 - 8\,192 &=7\,541\\
7\,541 - 4\,096 &= 3\,445\\
3\,445- 2\,048 &=1\,397\\
1\,397-1\,024 &= 373\\
373 - 256 &= 117\\
117-64 &= 53\\
53 - 32 &= 21\\
21- 16 &= 5\\
5- 4 &=1.
\end{align*} Cela montre que :
\begin{align*}
343\,413 &= 262\,144+65\,536+8\,192\\
&\quad+4\,096+2\,048+1\,024\\
&\quad+256+64+32\\
&\quad+16+4+1.
\end{align*} Vous calculez les puissances suivantes :
\begin{align*}
5^{262\,144}\times 5^{65\,536}\times 5^{8\,192} &\equiv 475\,022\times 616\,146 \times 224\,684\\
&\equiv 65\,761\,165\,874\,653\,008\\
&\equiv 47\,873\,200\,782\times 1\,373\,653 + 856\,362\\
&\equiv 856\,362
\end{align*}\begin{align*}
5^{4\,096}\times 5^{2\,048}\times 5^{1\,024} &\equiv 651\,599\times 269\,234 \times 54\,913\\
&\equiv 9\,633\,530\,647\,480\,558\\
&\equiv 7\,013\,074\,369\times 1\,373\,653 + 1\,280\,601\\
&\equiv 1\,280\,601
\end{align*}\begin{align*}
5^{256}\times 5^{64}\times 5^{32} &\equiv 1\,202\,675\times 901\,128 \times 593\,373\\
&\equiv 643\,076\,365\,633\,990\,200\\
&\equiv 468\,150\,519\,551\times 1\,373\,653 + 1\,200\,397\\
&\equiv 1\,200\,397
\end{align*}\begin{align*}
5^{16}\times 5^{4}\times 5^{1} &\equiv 1\,141\,732 \times 625 \times 5\\
&\equiv 3\,567\,912\,500\\
&\equiv 2\,597\times 1\,373\,653 + 535\,659\\
&\equiv 535\,659.
\end{align*}Puis :
\begin{align*}
5^{343\,413} &\equiv 856\,362\times 1\,280\,601 \times 1\,200\,397 \times 535\,659\\
&\equiv 705\,154\,906\,313\,747\,945\,181\,126\\
&\equiv 513\,342\,821\,159\,163\,154 \times 1\,373\,653 +1\,199\,564\\
&\equiv 1\,199\,564.
\end{align*} Vous calculez $5^{686\,826}$ comme suit :
\begin{align*}
5^{686\,826} &\equiv 5^{343\,413\times 2}\\
&\equiv (5^{343\,413})^2\\
&\equiv 1\,199\,564^2\\
&\equiv 1\,438\,953\,790\,096\\
&\equiv 1\,047\,538\times 1\,373\,653+73\,782\\
&\equiv 73\,782.
\end{align*} Il a été démontré que :
\left\{\begin{align*}
5^{343\,413}&\not\equiv 1\\
5^{343\,413}&\not\equiv -1\\
5^{686\,826}&\not\equiv -1.
\end{align*} \right.Cela prouve que le nombre $1\,373\,653$ ne passe pas le test de Miller en base $5.$ Ainsi $1\,373\,653$ n’est pas un nombre premier.
Prolongements
Première partie
Soit $n$ un nombre entier impair supérieur ou égal à $3$ et strictement inférieur à $2\,047.$
Démontrez que $n$ est premier, si et seulement si, il passe le test de Miller en base $2.$
Deuxième partie
Soit $n$ un nombre entier impair supérieur ou égal à $3$ et strictement inférieur à $10\,000.$
Démontrez que $n$ est premier, si et seulement si, il passe le test de Miller en base $2$ et s’il n’appartient pas à l’ensemble $A$ suivant :
A=\{2\,047, 3\,277, 4\,033, 4\,681, 8\,321\}.Troisième partie
Soit $n$ un nombre entier impair ou égal à $3$ et strictement inférieur à $1\,373\,653.$
Démontrez que $n$ est premier, si et seulement si, il passe le test de Miller en base $2$ et en base $3.$
Partagez maintenant !
Aidez vos amis à découvrir cet article et à mieux comprendre le sujet.
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 !