Revisitons le crible d’Ératosthène (1ère partie)

Une des premières choses qu’on apprend lorsqu’on découvre les nombres premiers est le crible d’Ératosthène. Il s’agit de faire un tableau dans lequel on place tous les nombres entiers naturels les uns à la suite des autres. Le principe est le suivant: on commence par barrer les multiples successifs de 2. Puis, on recommence avec le premier nombre dans la liste qui n’a pas été barré (en l’occurrence 3). Etc. A la fin, les nombres qui n’ont pas été barrés sont les nombres premiers.

Voici le principe en animation (il s’agit d’un document de Wikipédia sur le crible d’Ératosthène. Étant sous licence libre, je me permets de reprendre ce fichier sur mon blog. J’ai soulagé ma conscience, on peut continuer):

Pour vous éviter de vous retaper toute l’animation juste pour voir le tableau final, voici ce qu’on obtient quand l’algorithme se termine:

Les nombres premiers sont tous ceux qui sont entourés.

Tout cela est tellement joli que le crible d’Ératosthène ferait presque passer les grilles de Motus pour de vulgaires grilles de Bingo. Bon, je commence à dire n’importe quoi, recentrons-nous sur l’objet de cet article. A ma connaissance, les cribles d’Ératosthène que j’ai vus avaient tous 10 colonnes (ce qui est naturel puisque nous utilisons le système décimal pour représenter les entiers).

Et si ce crible n’avait que 6 colonnes ? Voyons voir ce qu’il se passerait dans ce cas (pourquoi 6 d’ailleurs ?). Vous pouvez le faire vous-même: écrivez la liste des nombres entiers en revenant à la ligne toutes les 6 cases. Ensuite, procédez à l’algorithme d’Ératosthène (barrez chers amis, barrez !), et enfin entourez tous les nombres premiers. Que constatez-vous ?

T’as vraiment de belles colonnes, tu sais…

J’ai fait ce tableau pour vous. Les nombres sont répartis sur 6 colonnes, et j’ai coloré en rouge les cases contenant un nombre premier.

Etrange… Hormis 2 et 3, tous les nombres premiers sont contenus dans seulement deux colonnes: la première et la cinquième. Est-ce vrai tout le temps ? Qui me dit que le 4711ème nombre premier n’aura pas envie de faire chier son monde et d’être dans la 4ème colonne ? (je le connais, il en est capable). Et si cela est vrai tout le temps, voyez-vous pourquoi ?

Explication

Je vous rassure tout de suite, notre conjecture est la bonne, à savoir que tout nombre premier différent de 2 et de 3 se situe nécessairement dans la première ou dans la cinquième colonne.

Soit p un nombre premier différent de 2 et de 3. Puisqu’on a découpé le tableau en 6 cases, on va faire la division euclidienne de p par 6. Si on note r le reste alors on peut écrire p=6k+r avec r<6.

Le nombre r peut potentiellement prendre les valeurs 0, 1, 2, 3, 4 ou 5.

• Si r=0 alors p=6k, donc p est divisible par 6, ce qui est impossible car p est un nombre premier.
• Si r=2 alors p=6k+2=2(3k+1) donc p est divisible par 2, ce qui entraine p=2. Nous avons supposé p différent de 2, donc ce cas est impossible.
• Si r=3 alors p=6k+3=3(2k+1) donc le même argument que précédemment (en remplaçant 2 par 3) montre que ce cas est impossible.
• Si r=4 alors p=6k+4=2(3k+2) donc p est divisible par 2, ce qui est impossible encore.

Au final, il ne reste que deux possibilités: r=1 ou r=5. Un nombre premier p différent de 2 et de 3 est donc toujours de la forme 6k+1 ou 6k+5.

Vous voyez le lien avec le tableau ? Puisqu’on a fait 6 colonnes, dans la 6ème colonne il y aura tous les multiples de 6, c’est-à-dire les nombres de la forme 6k. Dans la 1ère colonne, il y aura les nombres de la forme 6k+1. Dans la deuxième colonne, ce seront les nombres de la forme 6k+2. Etc.

Puisqu’un nombre premier (différent de 2 et de 3) est de la forme 6k+1 ou 6k+5, il sera donc forcément dans la première ou la cinquième colonne.

(Vous aurez remarqué que les deuxième et quatrième colonnes ne contiennent que des nombres pairs, la sixième colonne ne contient que des multiples de 6 et la troisième colonne ne contient que des multiples de 3 impairs… chose que nous avons prouvé en fait un peu plus haut si vous observez bien, lorsqu’on a examiné tous les cas de figures possibles pour le reste r).

A voir:

Pour un article qui utilise cette propriété des nombres premiers, vous pouvez vous rendre sur cet article de ce blog intitulé Un test de primalité… qui ne sert à rien. En fait, cette propriété est plutôt utilisée sous la forme (équivalente) suivante: un nombre premier différent de 2 et de 3 est de la forme 6k+1 ou 6k-1.

Et pour la deuxième partie de cet article, c’est par ici !