Découvrir
Pour trouver tous les nombres premiers jusqu'à 100, Ératosthène (276–194 av. J.-C.) avait une astuce simple. Laquelle, à ton avis ?
- Barrer les multiples de 2, puis de 3, de 5, de 7… : ce qui reste est premier
- Tester chaque nombre en le divisant par tous les nombres plus petits
L'idée clé
Nombres premiers, diviseurs et multiples dans l'histoire.
- Étape 1Euclide vers 300 av. J.-C.Portrait imaginéAuteur inconnu. Domaine publicVers 300 av. J.-C. : le livre VII des Éléments et l'algorithme d'Euclide.
- Étape 2Ératosthène vers 276 – vers 194 av. J.-C.Portrait imaginéAuteur inconnu. Domaine publicÉratosthène (276–194 av. J.-C.) : le crible des nombres premiers.
Le livre VII des Éléments d'Euclide (vers 300 av. J.-C.) est une introduction à la théorie des nombres et contient l'algorithme d'Euclide pour le PGCD. Ératosthène de Cyrène (276–194 av. J.-C.), qui a aussi mesuré la Terre, est connu pour son crible des nombres premiers.
Les nombres premiers sont plus nombreux que toute quantité proposée de nombres premiers.
Qu'affirme Euclide ?
- Il n'y a pas de plus grand nombre premier : ils ne s'arrêtent jamais
- Il y a exactement autant de nombres premiers qu'il en a listé
Exemple corrigé
L'algorithme d'Euclide pour le PGCD de 84 et 36.
Entraînement ★
- Pour quoi se souvient-on d'Ératosthène en théorie des nombres ?
- Son crible des nombres premiers
- L'algorithme du PGCD
- Les nombres négatifs
- Première étape de l'algorithme d'Euclide : quel est le reste de la division de 42 par 9 ?
- Première étape de l'algorithme d'Euclide : quel est le reste de la division de 271 par 33 ?
- Crible d'Ératosthène sur les nombres de 1 à 42 : après avoir barré les multiples de 2 (sauf 2), combien de nombres restent ?
Fiche résumé
Les nombres premiers aujourd'hui
- Les paiements en ligne sont protégés par des codes construits avec d'immenses nombres premiers.
- On simplifie une fraction en divisant par le PGCD.
- Calendriers et engrenages se répètent au bout d'un PPCM.
Sources : biographies d'Euclide et d'Ératosthène sur MacTutor (voir « Sources et crédits »).