Nombres Premiers

TL;DR

Un nombre premier est un nombre entier naturel supérieur à 1 qui n'a que deux diviseurs distincts : 1 et lui-même. Identifier les nombres premiers est essentiel en cryptographie et en théorie des nombres. La méthode principale pour les trouver est le crible d'Ératosthène, qui élimine les multiples des nombres déjà connus.

1. The Mental Model

Imaginez une armée de nombres entiers positifs. Les nombres premiers sont les "soldats fondamentaux" de cette armée ; vous ne pouvez pas les décomposer en des groupes plus petits d'autres soldats (sauf un soldat unique ou un groupe de lui-même). Chaque autre soldat (nombre composé) peut être formé en multipliant ces soldats fondamentaux.

2. The Core Material

Un nombre premier est un entier naturel ($>1$) qui n'est divisible que par 1 et par lui-même. C'est une définition simple mais puissante. Par exemple, 7 est premier car ses seuls diviseurs sont 1 et 7. En revanche, 6 n'est pas premier car il est divisible par 1, 2, 3 et 6.

Qu'est-ce qu'un Diviseur ?

Photo by Bakr Magrabi on Pexels

Un diviseur d'un nombre $N$ est un entier $d$ tel que $N \div d$ donne un résultat entier sans reste. Par exemple, les diviseurs de 12 sont 1, 2, 3, 4, 6 et 12.

Pourquoi 1 n'est pas un Nombre Premier ?

Photo by Mohan Nannapaneni on Pexels

Bien que 1 ne soit divisible que par 1 et lui-même (qui est aussi 1), il n'est pas considéré comme premier par convention. Cette convention simplifie de nombreuses théories mathématiques, notamment le Théorème Fondamental de l'Arithmétique, qui stipule que tout entier naturel supérieur à 1 peut être écrit comme un produit unique de nombres premiers. Si 1 était premier, cette unicité serait compromise (par exemple, $6 = 2 \times 3$ et $6 = 1 \times 2 \times 3$).

Le Crible d'Ératosthène

Photo by Geert Willemarck on Pexels

Le crible d'Ératosthène est une méthode efficace pour trouver tous les nombres premiers jusqu'à une certaine limite. Voici comment il fonctionne :

1. Listez tous les nombres entiers de 2 jusqu'à votre limite.
2. Commencez par le premier nombre non barré, qui est 2. C'est un nombre premier.
3. Barrez tous les multiples de 2 (4, 6, 8, ...).
4. Passez au prochain nombre non barré, qui est 3. C'est un nombre premier.
5. Barrez tous les multiples de 3 (6, 9, 12, ...). Certains peuvent déjà être barrés.
6. Répétez ce processus avec le prochain nombre non barré jusqu'à ce que vous ayez atteint la racine carrée de votre limite. Tous les nombres non barrés restants sont premiers.

graph TD
    A["Créer une liste de nombres de 2 à N"] --> B{"Est-ce que le carré du nombre courant est > N ?"};
    B -- Non --> C["Prendre le plus petit nombre non barré (p)"];
    C --> D["Marquer p comme premier"];
    D --> E["Barrez tous les multiples de p (2p, 3p, ...)"];
    E --> C;
    B -- Oui --> F["Tous les nombres non barrés sont premiers"];

Tests de Primalité (pour un seul nombre)

Photo by Jan Kopřiva on Pexels

Pour vérifier si un grand nombre $N$ est premier, vous pouvez tester sa divisibilité par tous les nombres premiers de 2 jusqu'à $\sqrt{N}$. Si $N$ n'est divisible par aucun d'entre eux, alors $N$ est premier.

Par exemple, pour savoir si 101 est premier :
* $\sqrt{101} \approx 10.05$. Nous devons tester les diviseurs jusqu'à 10.
* Les nombres premiers à tester sont 2, 3, 5, 7.
* 101 n'est pas divisible par 2 (il est impair).
* $1+0+1 = 2$, donc 101 n'est pas divisible par 3.
* 101 ne se termine pas par 0 ou 5, donc pas divisible par 5.
* $101 = 7 \times 14 + 3$, donc pas divisible par 7.
* Puisqu'il n'est divisible par aucun de ces nombres premiers, 101 est un nombre premier.

3. Worked Example

Utilisons le crible d'Ératosthène pour trouver tous les nombres premiers jusqu'à 30.

1. Liste initiale : 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30.
2. Le premier nombre non barré est 2. C'est un premier.
   • Barrez tous les multiples de 2 : 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30.
   • Liste : 2, 3, X, 5, X, 7, X, 9, X, 11, X, 13, X, 15, X, 17, X, 19, X, 21, X, 23, X, 25, X, 27, X, 29, X.
3. Le prochain nombre non barré est 3. C'est un premier.
   • Barrez tous les multiples de 3 : 6 (déjà barré), 9, 12 (déjà barré), 15, 18 (déjà barré), 21, 24 (déjà barré), 27, 30 (déjà barré).
   • Liste : 2, 3, X, 5, X, 7, X, X, X, 11, X, 13, X, X, X, 17, X, 19, X, X, X, 23, X, 25, X, X, X, 29, X.
4. Le prochain nombre non barré est 5. C'est un premier.
   • $\sqrt{30} \approx 5.47$. Nous devons aller jusqu'à 5.
   • Barrez tous les multiples de 5 : 10 (déjà barré), 15 (déjà barré), 20 (déjà barré), 25, 30 (déjà barré).
   • Liste : 2, 3, X, 5, X, 7, X, X, X, 11, X, 13, X, X, X, 17, X, 19, X, X, X, 23, X, X, X, X, X, 29, X.
5. Le prochain nombre non barré est 7. C'est un premier.
   • Les multiples de 7 (14, 21, 28) sont déjà barrés.
6. Tous les nombres premiers jusqu'à $\sqrt{30}$ (soit 5) ont été traités. Tous les nombres restants non barrés sont premiers.

Les nombres premiers jusqu'à 30 sont : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

4. Key Takeaways

• Un nombre premier est un entier naturel ($>1$) qui n'a que 1 et lui-même comme diviseurs.
• 1 n'est pas un nombre premier pour maintenir l'unicité de la décomposition en facteurs premiers.
• Le crible d'Ératosthène est une méthode efficace pour trouver tous les nombres premiers jusqu'à une certaine limite $N$.
• Pour tester si un grand nombre est premier, il suffit de vérifier la divisibilité par les nombres premiers jusqu'à sa racine carrée.
• Les nombres premiers sont les "briques de base" de tous les autres nombres entiers (composés) via la multiplication.

Common Mistakes:
- Oublier que 1 n'est pas premier et l'inclure dans la liste.
- Confondre un nombre impair avec un nombre premier (par exemple, 9 est impair mais n'est pas premier).
- Ne pas aller jusqu'à la racine carrée de $N$ lors des tests de primalité, ce qui peut manquer des diviseurs.

5. Now Try It

Utilisez la méthode du crible d'Ératosthène pour trouver tous les nombres premiers jusqu'à 50. Commencez par une liste de nombres de 2 à 50 et barrez systématiquement les multiples des nombres premiers que vous identifiez. La réussite signifie que vous obtenez la liste correcte des nombres premiers et que vous pouvez expliquer pourquoi vous avez barré certains nombres à chaque étape.