Les briques élémentaires des entiers

Qu'est-ce qu'un nombre premier ?

Certains entiers se décomposent, d'autres non. Ces derniers — les nombres premiers — sont les briques élémentaires à partir desquelles tous les autres se construisent.

La définition

Un entier n ≥ 2 est premier s'il n'admet que deux diviseurs positifs : 1 et lui-même.

Un entier n ≥ 2 qui n'est pas premier est dit composé : il s'écrit n = a × b avec a et b strictement compris entre 1 et n.

premiers  :  2   3   5   7   11   13   17   19   23   29   31 ...
composés  :  4=2×2   6=2×3   8=2×4   9=3×3   10=2×5   12=3×4 ...

2 est le seul nombre premier pair : tout autre nombre pair est divisible par 2, donc composé. C'est pour cette raison qu'on l'appelle parfois « le plus impair des nombres premiers ».

Pourquoi 1 n'est pas premier

Ce n'est pas un caprice de notation. 1 n'a qu'un seul diviseur, alors que la définition en exige exactement deux. Mais la vraie raison est ailleurs : si 1 était premier, l'unicité de la décomposition tomberait.

12 = 2 × 2 × 3
   = 1 × 2 × 2 × 3
   = 1 × 1 × 2 × 2 × 3          une infinité d'écritures !

Exclure 1 est ce qui permet d'énoncer le théorème fondamental de l'arithmétique sans exception. Les mathématiciens du XIXe siècle le comptaient encore parmi les premiers ; ils y ont renoncé pour cette raison précise.

Le crible d'Ératosthène

Pour trouver tous les premiers jusqu'à une borne, on n'en teste aucun : on élimine les composés.

1. écrire les entiers de 2 à N
2. entourer 2, puis rayer tous ses multiples : 4, 6, 8, 10 ...
3. entourer le plus petit nombre non rayé (3), rayer ses multiples : 6, 9, 12 ...
4. recommencer jusqu'à dépasser √N
5. les nombres non rayés sont les premiers

 2   3   4   5   6   7   8   9  10
11  12  13  14  15  16  17  18  19  20

après élimination :

 2   3   ·   5   ·   7   ·   ·   ·
11   ·  13   ·   ·   ·  17   ·  19   ·

Huit nombres premiers en dessous de 20. Ce crible, imaginé au IIIe siècle avant notre ère, reste la méthode la plus efficace pour lister tous les premiers d'un intervalle.

Tester un nombre isolé : s'arrêter à la racine

Pour savoir si n est premier, il est inutile de tester tous les diviseurs jusqu'à n - 1.

Si n est composé, il admet un diviseur inférieur ou égal à √n.

En effet, si n = a × b avec a > √n et b > √n, alors a × b > n : contradiction. L'un des deux facteurs est donc forcément ≤ √n.

97 est-il premier ?     √97 ≈ 9,8

on teste 2, 3, 5, 7    (les premiers ≤ 9)
   97 impair, non divisible par 3 (9+7=16), ni par 5, ni par 7 (7×13=91, 7×14=98)

   ->  97 est PREMIER

Quatre divisions au lieu de quatre-vingt-quinze. Le gain est spectaculaire : pour un nombre à 20 chiffres, on passe de 10²⁰ à 10¹⁰ tests — ce qui reste, on le verra, encore beaucoup trop.

En résumé