prime number

Prenez 29 jetons et cherchez à les répartir en rangées égales, sans jeton restant. Une seule rangée de 29 fonctionne, tout comme 29 rangées d’un jeton. Avec 2, 3, 4 ou 5 jetons par rangée, il reste toujours des jetons.

C’est l’idée d’un nombre premier : ses seuls diviseurs positifs sont 1 et lui-même. Le nombre 29 est donc premier. À l’inverse, un entier qui admet une autre répartition exacte est composé.

Un nombre premier est un entier naturel strictement supérieur à 1 qui possède exactement deux diviseurs entiers positifs distincts : 1 et lui-même. On note n l’entier étudié et d un diviseur positif. Le critère complet s’écrit $n>1\text{et}\mathrm{\#}\{d\in {\mathbb{N}}^{\ast }:d\mid n\}=2n>1\backslash quad\backslash text\{et\}\backslash quad\; \backslash \#\backslash \{d\backslash in\backslash mathbb\{N\}^*:d\backslash mid\; n\backslash \}=2$.

Un entier supérieur à 1 qui possède d’autres diviseurs positifs est composé. Les nombres 0 et 1 ne sont ni premiers ni composés. Tout entier composé se décompose de manière unique, à l’ordre des facteurs près, en produit de nombres premiers : c’est le théorème fondamental de l’arithmétique.

Il existe une infinité de nombres premiers. Des tests de primalité déterminent si un entier donné est premier. Leur étude, développée depuis l’Antiquité, intervient notamment en cryptographie et se relie à des structures algébriques et topologiques. Elle distingue des familles comme les nombres premiers de Fermat ou de Mersenne et laisse ouvertes des conjectures, dont celle de Goldbach.

Données. L’entier étudié est 29. Les diviseurs candidats à contrôler sont 2, 3, 4 et 5, car 5² = 25 et 6² = 36 encadrent 29.

1. La division par 2 donne 29 = 2 × 14 + 1. Le reste 1 montre que 2 ne divise pas 29.

2. La division par 3 donne 29 = 3 × 9 + 2. Le reste 2 montre que 3 ne divise pas 29.

3. La division par 4 donne 29 = 4 × 7 + 1. Le reste 1 montre que 4 ne divise pas 29.

4. La division par 5 donne 29 = 5 × 5 + 4. Le reste 4 montre que 5 ne divise pas 29.

Une représentation des 29 unités en paquets rend visibles ces quatre restes non nuls. Aucun diviseur candidat ne partage donc 29 exactement.

Résultat et contrôle. Les seuls diviseurs positifs de 29 sont 1 et 29 : 29 est premier. Le contrôle est refaisable avec les quatre divisions précédentes : tout diviseur non trivial supérieur à la racine carrée de 29 aurait un diviseur complémentaire inférieur à cette racine, déjà contrôlé.

Pour décider si un entier donné comme 29 est premier, on applique un test de primalité. Si une division exacte par un diviseur non trivial apparaît, on abandonne le verdict « premier » et on recherche plutôt sa factorisation.

Pour décomposer un entier composé, les nombres premiers servent de facteurs élémentaires. Le théorème fondamental de l’arithmétique garantit que le produit obtenu est unique, à l’ordre des facteurs près.

En cryptographie, les nombres premiers interviennent dans des applications majeures. Le choix entre tester la primalité et factoriser dépend du résultat recherché : certifier un entier dans le premier cas, décrire ses facteurs dans le second.

Nombre premier et nombre impair. Un entier impair n’est simplement pas divisible par 2, tandis qu’un nombre premier n’a aucun diviseur positif autre que 1 et lui-même. Le nombre 9 est impair mais composé, car 9 = 3 × 3.

Nombre premier et nombres premiers entre eux. « Premier » décrit un seul entier. « Premiers entre eux » compare deux entiers qui n’ont pas de diviseur positif commun autre que 1. Ainsi, 8 et 15 sont composés, mais premiers entre eux.

0 et 1. Le seuil « supérieur à 1 » est décisif. Même si 1 se divise par lui-même, il ne possède qu’un seul diviseur positif distinct ; 0 et 1 ne sont donc ni premiers ni composés.

Entiers négatifs. La définition donnée porte sur les entiers naturels. Pour décider de la primalité, on travaille donc avec un entier naturel supérieur à 1, sans étendre silencieusement le mot aux nombres négatifs.

Suite et test. Produire la suite des nombres premiers et tester un entier fixé sont deux problèmes différents. Pour le second, de nombreux tests de primalité permettent d’obtenir un verdict.

Record daté. Le nombre 2^43112609 − 1, nombre de Mersenne de près de 13 millions de chiffres décimaux, était le plus grand premier connu en 2008. Cette date empêche de le présenter comme un record actuel.

Factorisation — Voir comment un entier composé se réécrit en facteurs, jusqu’à sa décomposition en nombres premiers.

nombre de Mersenne — Approfondir une famille particulière liée à la recherche de très grands nombres premiers.

conjecture de Goldbach — Suivre une question ouverte célèbre née de l’étude additive des nombres premiers.

L'inépuisable théorème des nombres premiers — Prolonger l’infinité des premiers par l’étude de leur répartition parmi les entiers.