Revisitons le crible d’Ératosthène (2ème partie)

Dans le précédent article, nous avions vu que lorsqu’on représente le crible d’Ératosthène dans un tableau à seulement 6 colonnes, alors, hormis 2 et 3, tous les nombres premiers sont contenus dans la première ou la cinquième colonne. Plus précisément, voici le tableau que nous avions obtenu:

La question qu’on peut alors se poser est celle de savoir si la répartition des nombres premiers se fait toujours sur les deux colonnes, ou bien si, par exemple, la première colonne ne contient plus aucun nombre premier à partir d’un certain moment.

Plagions Euclide

En fait nous allons montrer que la première colonne contient une infinité de nombres premiers. Et de même pour la cinquième colonne. Et nous allons commençons par la cinquième colonne (plus simple).

Rappelons que les nombres de la cinquième colonne sont tous les nombres de la forme 6k+5. Pour montrer que la cinquième colonne contient une infinité de nombres premiers, nous allons montrer qu’il existe une infinité de nombres premiers de la forme 6k+5. Pour ce faire, nous allons adapter la preuve d’Euclide de l’infinité des nombres premiers. C’est donc une preuve par l’absurde que nous allons effectuer.

Supposons qu’il existe un nombre fini de nombres premiers $p_1 < p_2 < \cdots < p_k$ de la forme 6k+5. Le début de cette suite est donc $p_1=5$ , $p_2=11$ , etc. Posons

$N= 2 \times 3 \times p_1 \times p_2 \times \cdots \times p_k -1$

Puisque $N$ est de la forme 6k-1, on a donc $N \equiv - 1 \equiv 5 [6]$ . D’autre part, si $q$ est un diviseur premier de $N$ , alors $q$ ne peut être de la forme 6k+5. En effet, si tel était le cas, alors on aurait $q=p_i$ pour un certain $i$ donc q diviserait le produit $2 \times 3 \times p_1 \times p_2 \times \cdots \times p_k$ . Donc $q$ diviserait $N - 2 \times 3 \times p_1 \times p_2 \times \cdots \times p_k$ c’est-à-dire que $q$ diviserait -1, ce qui est impossible car $q$ est premier. D’autre part, $N$ n’est divisible ni par 2, ni par 3 (car il est de la forme 2r+1 et de la forme 3m+2) donc tous les facteurs premiers de $N$ sont de la forme 6k+1.

Or, le produit de deux nombres premiers congrus à 1 modulo 6 est encore congru à 1 modulo 6 (je ne fais que dire que si $q_1 \equiv 1 [6]$ et si $q_2 \equiv 1 [6]$ alors $q_1 q_2 \equiv 1 [6]$ ). On en déduit donc que $N \equiv 1 [6]$ , ce qui contredit le fait que $N \equiv 5 [6]$ .

Encore du boulot…

En ce qui concerne la première colonne, il va falloir un peu plus de travail pour montrer qu’elle contient une infinité de nombres premiers. Commençons par prouver le lemme suivant:

Soit p un nombre premier supérieur strictement à 3. Alors les propositions suivantes sont équivalentes:
(i) -3 est un carré modulo p c’est-à-dire s’il existe un entier x tel que $-3 \equiv x^2 [p]$ .
(ii) $p \equiv 1 [6]$ .

Une manière « simple » de prouver cela est d’utiliser la loi de réciprocité quadratique (soit la grosse artillerie). Pour ceux qui n’ont jamais entendu parlé de cette loi, admettez ce lemme, fermez les yeux et sautez vers le paragraphe suivant.

Preuve du lemme: Puisque le symbole de Legendre est multiplicatif, on peut écrire:

$\left(\frac{-3}{p}\right) = \left(\frac{-1}{p}\right) \left(\frac{3}{p}\right)$

Donc

$\left( \frac{-3}{p} \right) = (-1)^{\frac{p-1}{2}} \left( \frac{3}{p} \right)$

Or d’après la belle loi de réciprocité quadratique,

$\left( \frac{3}{p} \right) \left( \frac{p}{3} \right) = (-1)^{\frac{(p-1)(3-1)}{4}}=(-1)^{\frac{p-1}{2}}$

Donc

$\left(\frac{3}{p}\right) = \left(\frac{p}{3}\right) (-1)^{\frac{p-1}{2}}$

D’où (ça change du donc)

$\left( \frac{-3}{p} \right) = (-1)^{\frac{p-1}{2}} \left( \frac{p}{3} \right) (-1)^{\frac{p-1}{2}}$

Donc

$\left( \frac{-3}{p}\right) = \left( \frac{p}{3} \right)$

On en déduit donc que -3 est un carré modulo p si et seulement si p est un carré modulo 3. Or, p est un nombre premier supérieur strictement à 3 donc il est de la forme 6k+1 ou 6k+5. D’autre part, puisque

$\begin{array}{c|c|c|c} n & 0 & 1 & 2 \\ \hline n^2 \text{ mod 3} & 0 & 1 & 1 \\ \end{array}$

alors p est un carré modulo 3 si et seulement si $p\equiv 1 [3]$ (en effet, puisque $p$ est premier supérieur strictement à 3, le cas $p \equiv 0 [3]$ est à exclure). Mais puisque $6k+5 \equiv 2 [3]$ , on ne peut avoir $p$ de la forme 6k+5. Donc -3 est un carré modulo p si, et seulement si, p est de la forme 6k+1.

Infinité de nombres premiers dans la première colonne

A présent, nous sommes en mesure de prouver qu’il existe une infinité de nombres premiers de la forme 6k+1. Là encore, nous allons faire une preuve par l’absurde.

Supposons qu’il existe un nombre fini de nombres premiers $p_1 < p_2 < \cdots < p_k$ de la forme 6k+1. Le début de cette suite est donc $p_1=7$ , $p_2=13$ , … On pose

$N = (2 \times p_1 \times p_2 \times \cdots \times p_k)^2+3$

Soit $q$ un diviseur premier de $N$ . Tout d’abord, $q$ ne peut pas être 2 car le nombre $N$ est de la forme 2k+3 c’est-à-dire que $N$ est impair (donc pas divisible par 2). De plus, $q$ ne peut valoir 3 car autrement, 3 diviserait $N - 3 = (2 \times p_1 \times p_2 \times \cdots \times p_k)^2$ et donc, puisque 3 est premier, ou bien il serait égal à 2 (impossible) ou bien il serait égal à l’un des $p_i$ ce qui est impossible aussi car $3 \equiv 3 [6]$ (lol) et que pour tout i, $p_i \equiv 1 [6]$ .

Donc, l’entier $N$ admet un diviseur premier $q$ strictement supérieur à 3. Or, $N \equiv 0 [q]$ donc $(2 \times p_1 \times \cdots \times p_k)^2 \equiv -3 [q]$ ce qui signifie que -3 est un carré modulo q. D’après le lemme, cela implique que $q$ est de la forme 6k+1. Par suite, $q$ est un des $p_i$ , donc $q$ divise $(2 \times p_1 \times \cdots \times p_k)^2$ . Puisqu’il divise aussi $N$ , il divise $N - (2 \times p_1 \times \cdots \times p_k)^2 = 3$ . Donc $q=3$ ce qui est impossible comme on l’a montré ci-dessus.

Retour au crible…

Nous pouvons généraliser tout ce que nous venons de voir. On se donne $n$ un entier positif supérieur ou égal à 2. On effectue le crible d’Ératosthène dans un tableau à $n$ colonnes. Soit $k$ un entier compris entre 1 et $n$ . Un formidable théorème dû à Dirichlet affirme que si $k$ est premier avec $n$ alors la $k$ -ième colonne contiendra une infinité de nombre premiers. Il s’agit du théorème de la progression arithmétique qui dit que si $n$ et $k$ sont deux nombres premiers entre eux, il existe une infinité de nombres premiers de la forme $qn+k$ ( $q$ entier naturel). En particulier, si $n$ est un nombre premier, toutes les colonnes contiendront une infinité de nombres premiers sauf une.

Nous venons dans cet article de prouver le théorème de Dirichlet dans le cas particulier $n=6$ et $k$ = 1 et 5 (non sans peine !). Le cas général est infiniment plus compliqué bien entendu. Ce qui est amusant, c’est que ce théorème d’arithmétique se démontre classiquement à l’aide de l’analyse complexe.

Et pour finir cet article, voici le crible d’Ératosthène dans un tableau à 8 colonnes ! (dans la colonne de droite, la table de 8, pour ceux qui l’auraient oubliée…)

7 commentaires pour Revisitons le crible d’Ératosthène (2ème partie)

Ping : Revisitons le crible d’Ératosthène | Blogdemaths
calculatrice dit :

9 septembre 2012 à 16 h 04 min

Super article ! Merci

J’aimeJ’aime

Réponse
- blogdemaths dit :
  
  9 septembre 2012 à 18 h 40 min
  
  De rien 🙂
  
  J’aimeJ’aime
  
  Réponse
Émilie Mazzella dit :

30 août 2013 à 9 h 09 min

Bonjour,
Pour être revenu sur votre démonstration, dans la première partie, je crois qu’il faut plutôt dire que divisant N d’une part et le produit d’autre part, q diviserait la différence qui vaut 5 et non 1 comme spécifié.
Cordialement,
Denise Chemla

J’aimeJ’aime

Réponse
- blogdemaths dit :
  
  30 août 2013 à 17 h 57 min
  
  Effectivement, il y a un petit souci. Il fallait lire
  $N= 2 \times 3 \times p_1 \times p_2 \times \cdots \times p_k -1$
  au lieu de
  $N= 2 \times 3 \times p_1 \times p_2 \times \cdots \times p_k +5$
  , le reste de la démonstration étant inchangé.
  
  Cela a été corrigé dans l’article. Merci pour votre vigilance.
  
  J’aimeJ’aime
  
  Réponse
Émilie Mazzella dit :

29 septembre 2013 à 8 h 24 min

De rien. Merci à vous, c’est effectivement un très beau post.

Et pour ma question du 28 août, 13 h 14, rien de rien ?…

Cordialement.

J’aimeJ’aime

Réponse
- blogdemaths dit :
  
  2 octobre 2013 à 19 h 18 min
  
  Bonjour,
  
  Malheureusement, je n’ai ni le temps, ni les compétences requises pour lire votre démonstration. Si elle est correcte, l’Histoire (avec un grand H) saura vous rendre hommage de toutes façons !
  
  J’aimeJ’aime
  
  Réponse