Qu'est-ce que « Nombre premier » ? — Mathématiques

Définition 64.5 Mathématiques du primaire et du collège · Chapitre 64 — Arithmétique : diviseurs et nombres premiers

Un nombre premier est un entier $\geq 2$ dont les seuls diviseurs sont $1$ et lui-même. Les premiers inférieurs à $30$ sont

2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29 .

Le nombre $1$ n’est pas premier (par convention), et un entier $\geq 2$ qui n’est pas premier s’appelle composé.

L’arbre de facteurs de 360 : chaque étape détache le plus petit facteur premier (en rouge). En lisant les feuilles rouges et le 5 final : 360 = 23 × 32 × 5. — L’arbre de facteurs de $360$ : chaque étape détache le plus petit facteur premier (en rouge). En lisant les feuilles rouges et le $5$ final : $360 = 2^3 \times 3^2 \times 5$ .

Lire dans le chapitre →

Définition 6.12 Mathématiques universitaires — Licence 1 · Chapitre 6 — Arithmétique des entiers

Un entier $p \geq 2$ est premier lorsque ses seuls diviseurs positifs sont $1$ et $p$ . Pour $p$ premier et $a \in \Z$ : ou bien $p \mid a$ , ou bien $\gcd(p, a) = 1$ . Par conséquent (Théorème 6.8), le lemme d’Euclide est vrai : si $p \mid ab$ , alors $p \mid a$ ou $p \mid b$ .

Exemples

Exemple 6.24 (La réciproque de Fermat est fausse : $341$ )

Le petit théorème de Fermat fournit un test de non-primalité bon marché : si $a^{n-1} \not\equiv 1 \pmod n$ pour un certain $a$ premier avec $n$ , alors $n$ n’est pas premier. Le test pourrait-il aussi certifier la primalité ? Non : prenons $n = 341 = 11 \times 31$ , composé, et $a = 2$ . Comme $2^{10} = 1024 = 3 \times 341 + 1$ ,

2^{10} \equiv 1 \pmod{341} \qquad\Longrightarrow\qquad 2^{340} = \bigl(2^{10}\bigr)^{34} \equiv 1 \pmod{341} :

le nombre composé $341$ passe le test de Fermat en base $2$ (c’est le plus petit pseudo-premier de ce genre). La base $3$ le démasque ( $3^{340} \not\equiv 1$ ), et les tests de primalité pratiques exécutent donc le test sur plusieurs bases, avec des raffinements — les versions industrielles de cette idée sont celles qui certifient les grands nombres premiers de la Remarque 6.27. Morale : une implication et sa réciproque mènent des vies séparées (Remarque 1.10), même pour les théorèmes.

Lire dans le chapitre →

Exemples

Termes liés