Nombres Premiers

Un nombre premier est un entier naturel supérieur ou égal à 2 qui admet exactement deux diviseurs positifs distincts : $ 1 $ et lui-même.

Mathématiquement, un entier $ p $ est premier si $ p \ge 2 $ et si ses seuls diviseurs positifs sont 1 et $ p $.

Les nombres premiers possèdent plusieurs propriétés fondamentales. Tout d'abord, il existe une infinité de nombres premiers. Euclide l'a démontré il y a plus de 2000 ans : si une liste contenait tous les nombres premiers $ p_1, p_2, \ldots, p_n $, le nombre $ N = p_1 \times p_2 \times \ldots \times p_n + 1 $ ne serait divisible par aucun des $ p_i $, car la division par chacun d'eux laisserait un reste de 1. Le nombre $ N $ serait donc lui-même premier ou posséderait un facteur premier absent de la liste, ce qui conduit à une contradiction.

Les nombres premiers deviennent également plus rares lorsque les entiers augmentent. Si $ \pi(x) $ désigne le nombre de nombres premiers inférieurs ou égaux à $ x $, le théorème des nombres premiers donne : $ \pi(x) \sim \frac{x}{\ln(x)} $ Autrement dit, la proportion d'entiers proches de $ x $ qui sont premiers est approximativement $ 1/\ln(x) $.

La répartition des nombres premiers n'est cependant pas périodique ni décrite par une formule élémentaire simple. Des résultats et conjectures plus avancés, notamment l'hypothèse de Riemann, cherchent à préciser cette répartition et les écarts autour des approximations données par le théorème des nombres premiers.

Il existe plusieurs familles de nombres premiers remarquables.

— Les nombres de Mersenne sont les nombres de la forme $ 2^p - 1 $, où $ p $ est un entier premier dans le cas généralement étudié pour rechercher des nombres premiers. Lorsqu'un tel nombre est effectivement premier, il est appelé nombre premier de Mersenne.

— Les nombres de Fermat sont les nombres de la forme $ F_n = 2^{2^n}+1 $. Les seuls nombres de Fermat connus pour être premiers sont : $ 3,\ 5,\ 17,\ 257,\ 65537 $ correspondant à $ n=0,1,2,3,4 $. À ce jour, aucun nombre de Fermat avec $ n \ge 5 $ dont la nature est connue n'est premier.

— Les nombres premiers jumeaux sont des paires de nombres premiers séparés de 2, comme $ (3,5) $, $ (5,7) $ et $ (11,13) $. La conjecture des nombres premiers jumeaux affirme qu'il existe une infinité de telles paires, mais cette affirmation n'est toujours pas démontrée.

— Un nombre premier de Sophie Germain est un nombre premier $ p $ tel que $ 2p+1 $ soit également premier.

— Un nombre premier de Wieferich est un nombre premier impair $ p $ vérifiant $ p^2 \mid 2^{p-1}-1 $. Les deux premiers exemples connus sont $ 1093 $ et $ 3511 $, et aucun autre n'est connu à ce jour dans les recherches publiées et répertoriées.

— Les nombres premiers palindromes sont des nombres premiers dont l'écriture dans une base donnée est un palindrome, comme 2, 3, 5, 7, 11, 101 ou 131.

— Un nombre premier circulaire est un nombre premier dont toutes les rotations circulaires des chiffres sont également premières dans la même base.

Les nombres premiers jouent un rôle important dans plusieurs domaines des mathématiques et de l'informatique.

— En cryptographie, ils sont notamment utilisés dans RSA : deux grands nombres premiers $ p $ et $ q $ sont multipliés pour former le nombre $ n=pq $. La sécurité repose notamment sur la difficulté, pour un attaquant, de retrouver les facteurs premiers $ p $ et $ q $ à partir de leur produit $ n $.

— Le protocole Diffie-Hellman utilise quant à lui le problème du logarithme discret dans un groupe cyclique. Une construction classique utilise le groupe multiplicatif d'un corps fini de taille première, ce qui fait intervenir directement l'arithmétique modulaire et les nombres premiers

— En informatique, les propriétés des nombres premiers interviennent aussi dans certains algorithmes de hachage, de génération pseudo-aléatoire, de théorie des algorithmes et de calcul modulaire.

— En biologie, les cigales périodiques du genre Magicicada constituent un exemple célèbre : certaines émergent tous les 13 ou 17 ans. Le caractère premier de ces cycles pourrait réduire certaines coïncidences avec d'autres cycles biologiques, mais plusieurs mécanismes évolutifs sont étudiés et aucune explication unique ne suffit à elle seule.

Le nombre 1 n'est pas premier car il n'a qu'un seul diviseur positif : lui-même. Cette convention est essentielle pour le théorème fondamental de l'arithmétique, selon lequel tout entier supérieur ou égal à 2 se décompose de manière unique, à l'ordre des facteurs près, en produit de nombres premiers.

Si 1 était considéré comme premier, cette unicité disparaîtrait : par exemple, $ 6 = 2 \times 3 $ pourrait aussi s'écrire $ 6 = 1 \times 2 \times 3 $, $ 6 = 1 \times 1 \times 2 \times 3 $, etc. Le nombre 1 joue donc un rôle particulier : c'est l'élément neutre de la multiplication, et non un nombre premier.