Le crible d’Ératosthène : pourquoi peut-on s’arrêter à la racine carrée ?

Pour savoir si 211 est premier, personne ne teste 210 divisions. On s’arrête à 13, parce que 14² = 196 et 15² = 225 encadrent 211. La règle est enseignée partout ; sa justification, presque nulle part. Elle tient pourtant en trois lignes, et ces trois lignes disent quelque chose de plus général que le test lui-même.

Cet article poursuit le fil ouvert par L’algorithme d’Euclide. Il complète deux publications antérieures sur les nombres premiers : Suite finie de nombres premiers et Une preuve topologique de l’infinité des nombres premiers. La preuve du lemme s’appuie par ailleurs, en un point, sur une récurrence forte ; Construire ℕ : les axiomes de Peano et l’origine de la récurrence en donne le fondement, et dit pourquoi la récurrence est un axiome et non une technique de rédaction.

1. Le crible

La méthode attribuée à Ératosthène de Cyrène, au III^e siècle avant notre ère, ne cherche pas les nombres premiers : elle élimine les autres. Écrivons les entiers de $2$ à $n$ , puis répétons deux gestes.

Entourer le plus petit nombre non encore rayé ni entouré : il est premier.
Rayer tous ses multiples stricts.

Sur les entiers jusqu’à $100$ : on entoure $2$ et l’on raye $4, 6, 8,\ldots$ ; on entoure $3$ et l’on raye $9, 15, 21,\ldots$ ; on entoure $5$ , puis $7$ . Vient le tour de $11$ — et là, on constate que tout est déjà fait. Les multiples de $11$ inférieurs à $100$ , soit $22, 33, 44, 55, 66, 77, 88, 99$ , ont tous été rayés auparavant. Les nombres qui restent debout sont les vingt-cinq nombres premiers inférieurs à $100$ .

Le crible s’est donc arrêté tout seul à $7$ , dernier nombre premier vérifiant $p^{2}\leq 100$ , puisque $11^{2}=121$ dépasse $100$ . Ce n’est pas un accident de l’exemple.

2. Le lemme qui borne la recherche

Lemme. Tout entier $n\geq 2$ non premier admet un diviseur premier $p$ vérifiant $p\leq\sqrt{n}$ .

Preuve. Soit $n\geq 2$ un entier non premier. Il s’écrit $n=ab$ avec $1<a\leq b<n$ ; quitte à échanger les deux facteurs, on peut en effet supposer $a\leq b$ . Alors

$\displaystyle a^{2}=a\times a\leq a\times b=n,$

d’où $a\leq\sqrt{n}$ . Par ailleurs $a\geq 2$ , donc $a$ admet un diviseur premier $p$ , et $p\leq a$ . Ce nombre $p$ divise $a$ , qui divise $n$ : il divise donc $n$ . Ainsi $p\leq a\leq\sqrt{n}$ . $\quad\Box$

Deux remarques sur cette preuve, courte mais moins innocente qu’elle n’en a l’air.

Le pas décisif est l’inégalité $a^{2}\leq ab$ . Il repose entièrement sur le choix $a\leq b$ , c’est-à-dire sur la liberté de nommer $a$ le plus petit des deux facteurs. C’est un exemple simple d’un procédé fréquent : on ne démontre rien de plus en supposant $a\leq b$ , mais on s’épargne la moitié du travail.

Le second pas — « $a\geq 2$ donc $a$ admet un diviseur premier » — est admis partout et se démontre par récurrence forte : si $a$ est premier, il est son propre diviseur premier ; sinon $a=cd$ avec $1<c<a$ , et $c$ admet déjà un diviseur premier, lequel divise $a$ .

3. Ce que le lemme autorise

Le lemme se lit surtout dans sa forme contraposée, qui est le test de primalité lui-même.

Test de primalité. Si aucun nombre premier $p\leq\sqrt{n}$ ne divise $n$ , alors $n$ est premier.

Reprenons $211$ . On a $14^{2}=196$ et $15^{2}=225$ , donc $\sqrt{211}$ est compris entre $14$ et $15$ . Les nombres premiers à tester sont $2, 3, 5, 7, 11, 13$ . Aucun ne divise $211$ : il est premier. Six divisions au lieu de deux cent neuf.

Dans le crible, le lemme dit exactement ceci : dès que le premier entouré $p$ vérifie $p^{2}>n$ , tout ce qui reste debout est premier. Les multiples de $p$ encore présents seraient de la forme $pm$ avec $m\geq p$ , donc au moins $p^{2}$ , donc hors du tableau. Mieux : lorsqu’on raye les multiples de $p$ , il est inutile de commencer à $2p$ — tous les multiples $kp$ avec $k<p$ portent un facteur premier plus petit que $p$ et ont déjà été rayés. On peut donc démarrer directement à $p^{2}$ .

4. Une borne, deux malentendus

La borne ne dit pas que les diviseurs sont petits. Elle dit que le plus petit l’est. L’entier $143=11\times 13$ a bien un diviseur inférieur à $\sqrt{143}\approx 11{,}96$ , à savoir $11$ ; son autre diviseur, $13$ , la dépasse. Les diviseurs d’un entier vont par paires $(a,b)$ de produit $n$ , et dans chaque paire l’un est en deçà de $\sqrt{n}$ , l’autre au-delà. C’est pourquoi la borne est optimale : la réduire ferait manquer les carrés de nombres premiers, comme $169=13^{2}$ , dont l’unique diviseur premier vaut exactement $\sqrt{169}$ .

Le test n’est pas une factorisation. Il répond « premier » ou « non premier », et dans le second cas il livre un facteur ; il ne donne pas la décomposition. La distinction est aujourd’hui l’un des piliers de la cryptographie : on sait tester rapidement la primalité de nombres de plusieurs centaines de chiffres, sans savoir les factoriser. La division par tous les premiers jusqu’à $\sqrt{n}$ reste d’ailleurs impraticable à cette échelle — pour $n$ de cent chiffres, il faudrait environ $10^{48}$ divisions — et les tests modernes procèdent tout autrement.

La borne $\sqrt{n}$ garde donc son domaine : les entiers que l’on manipule en classe, et la construction de tables de nombres premiers. Sur ce terrain-là, elle est ce qui sépare un calcul faisable d’un calcul absurde.

Le crible, les tests de divisibilité et la décomposition en facteurs premiers sont traités au chapitre 3 de Mathématiques en terminales scientifiques, Tome 2.

Formalis Mathematica

Rigueur et formalisme au cœur de l’apprentissage et de l’enseignement des mathématiques

Le crible d’Ératosthène : pourquoi peut-on s’arrêter à la racine carrée ?

1. Le crible

2. Le lemme qui borne la recherche

3. Ce que le lemme autorise

4. Une borne, deux malentendus

Laisser un commentaire Annuler la réponse.

1. Le crible

2. Le lemme qui borne la recherche

3. Ce que le lemme autorise

4. Une borne, deux malentendus

Partagez :

Similaire

Laisser un commentaire Annuler la réponse.