Infinité des nombres premiers et crible d'Ératosthène

Terminale générale Spé · Option Mathématiques Expertes

À retenir

• Il existe une infinité de nombres premiers (théorème d'Euclide). • Tout entier n 2 admet un diviseur premier ; si n est composé, il en a un qui vérifie p^2 n. • Crible jusqu'à N : barrer les multiples de chaque premier p à partir de p^2, tant que p^2 N.

Le cours

1. Théorème d'Euclide L'ensemble des nombres premiers est infini. Démonstration par l'absurde : supposons qu'il n'existe qu'un nombre fini de nombres premiers p_1, p_2, , p_k et posons N = p_1 p_2 p_k + 1. Comme N 2, N admet un diviseur premier q. Si q était l'un des p_i, il diviserait N et p_1 p_k, donc leur différence 1 : c'est impossible. Contradiction. 2. Lemme utile Tout entier n 2 admet un diviseur premier : son plus petit diviseur d > 1. Si n est composé, ce plus petit diviseur vérifie d^2 n. 3. Crible d'Ératosthène jusqu'à N 1. Écrire tous les entiers de 2 à N. 2. Le plus petit nombre non barré p est premier : barrer ses multiples à partir de p^2 (les plus petits sont déjà barrés). 3. Recommencer avec le nombre non barré suivant, tant que p^2 N. 4. Les nombres restants sont exactement les nombres premiers inférieurs ou égaux à N. 4. Attention La preuve d'Euclide n'affirme pas que p_1 p_2 p_k + 1 est premier : 2 3 5 7 11 13 + 1 = 30\,031 = 59 509. Elle montre seulement que ses diviseurs premiers sont nouveaux.

Dans ce chapitre