Ce sont les nombres qui admettent exactement deux diviseurs distincts (1 n'est donc pas premier).
Les cent premiers nombres premiers : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
Tout nombre entier se décompose de manière unique (à permutation et multiplication par +/-1 près) en produit de nombre premiers (démontré par Gauss en 1799) : ils correspondent approximativement au tableau de Mendeleïev des nombres.
Leur utilisation récente en cryptographie (cryptage RSA) les a placé sur le devant de la scène : les maîtriser devient un enjeu stratégique majeur.
Le plus grand nombre premier connu est un nombre premier de Mersenne. Il vaut $2^{32582657}-1$
Les algorithmes probabilistes de test de la primalité identifient des nombres premiers de 100000 chiffres en quelques fractions de secondes.
Il permet d'obtenir la liste des nombres premiers inférieurs à N :
Voici une petite liste de résultats connus, certains depuis longtemps, autour des nombres premiers...
$p\equiv 1[4] \Rightarrow \exists (m,n) \in \mathbb{N}^2, p = m^2+n^2$
Les résultats suivants restent à démontrer...
Le plus grand commun diviseur (aka PGCD) de $a$ et $b$ est le plus grand élément de l'ensemble des diviseurs communs à $a$ et $b$. C'est un entier positif.
Le plus petit commun multiple (aka PPCM) de $a$ et $b$ est le plus petit élément de l'ensemble des multiples communs à $a$ et $b$. C'est un entier positif.
Pour le PPCM de deux nombres, on peut utiliser le fait que $PPCM(a,b) = \frac{ab}{PGCD(a,b)}$.
Pour obtenir le PPCM des nombres compris entre 2 et un maximum donné, on procède comme dans le crible d'Eratosthène, en intercalant, pour chaque puissance d'un nombre premier, un facteur $p$ à la place de $p^n$.
Par exemple, le PPCM des entiers depuis 2 jusqu'à 10 est égal au produit des nombres 2,3,2,5,7,2,3, parce que 2,3,5 et 7 sont des nombres premiers, et que 4 et 8 sont remplacés par 2, et 9 par 3.
Rappelons que pour effectuer le calcul d'une puissance entière d'un nombre, il faut éviter de calculer $x^{100}$ en multipliant $x$ 99 fois par lui-même.
Par exemple, pour calculer $x^{100}$, on calculera $x^{64} \times x^{32} \times x^4$, soit 6 multiplications pour $x^{62}$, puis 2 multiplications pour terminer, donc au final 8 multiplications.
Pour décomposer le calcul comme cela a été fait précédemment, il faut utiliser la représentation binaire de l'exposant. Ainsi, $100_{10} = 1100100_2$, soit... $100 = 1 \times 2^6 + 1 \times 2^5 + 0 \times 2^4 + 0 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 0 \times 2^0 = 64 + 32 + 4.$
Si $n$ est représentable en machine, alors, aussi grand que soit l'exposant $p$, $a^p %n$ est représentable en machine.
Dans le calcul concret de cette puissance, il est cependant nécessaire d'utiliser temporairement des nombres supérieurs à $n$, avant de les réduire modulo $n$.
Cependant, comme il est primordial pour l'efficacité d'éviter l'apparition de très grands nombres entiers, au lieu de calculer par exemple $x^{100}$ puis réduire le résultat modulo $n$, la réduction modulo $n$ se fait après chaque multiplication.
Pour trouver les facteurs d'un entier n, on divise ce nombre, successivement, par tous les entiers inférieurs à $n$.
On pourrait se limiter à rechercher les restes des divisions de n par les nombres premiers inférieurs à $\sqrt{n}$, mais ce raffinement de la méthode impose l'utilisation d'une table des nombres premiers (générée par le crible d'Eratosthène, par exemple.)
Souvent, en l'absence de cette table, on opte pour un compromis : on teste la divisibilité par 2, puis par les nombres impairs seulement, ce qui fait $\approx \frac{\sqrt{n}}{2}$ divisions.
Une méthode alternative pour savoir si un nombre est premier, est d'utiliser le théorème de Wilson :
$n \textrm{ est premier } \Longleftrightarrow n \textrm{ divise } (n-1)!+1.$
Ainsi, par exemple, 10!+1=3628801 est divisible par 11 (la somme alternée des chiffres l'est), donc 11 est premier.
Hélas, cette méthode nécessite n multiplications (plus d'opérations que la précédente.)
Les tests de primalité modernes se fondent sur un résultat analogue, découvert dans la Chine antique:
$\textrm{Si n est premier, alors n divise } 2^n-2.$
Ainsi, chercher à savoir si 107 est premier revient à chercher s'il divise $2^{107}-2$. Or, il existe des méthodes d'exponentiation rapide qui permettent d'obtenir $2^{107}$ en moins d'une dizaine de multiplications.
Plus généralement, on sait calculer $2^n$ en moins de 3,4N multiplications, où N est le nombre de chiffres de n.
De plus, on ne souhaite pas calculer $2^n-2$, mais son modulo n. On a ainsi une méthode rapide, et qui n'encombre pas la mémoire.
Du fait de la non équivalence du résultat précédent, il existe des nombres qui divisent $2^n-2$, et qui ne sont pas premier. On les appelle nombre pseudo-premiers de base 2. Heureusement, ils sont rares.
341=11*31
La plupart de ces exceptions peuvent être traitées par une généralisation du test Chinois : le petit théorème de Fermat (à ne pas confondre avec le dernier théorème de Fermat, récemment devenu une star.)
Si $n$ est premier, alors $n$ divise $a^n-a, a>1$
En d'autres termes, $a^n \equiv a [n].$
Au lieu de tester uniquement si $n$ divise $2^n-2$, on peut regarder aussi si $n$ divise $3^n-3$, $5^n-5$, $7^n-7$, etc.
On peut alors, encore, trouver des exceptions (des nombres pseudo-premiers en base a), voire même des nombres pseudo-premiers dans plusieurs bases.
Par malchance, chaque base a une infinité de pseudo-premiers. Pire, il existe des nombres, dits de Carmichaël, qui sont pseudo-premiers dans toutes les bases n'ayant pas de facteur commun avec le nombre lui-même.
Par exemple, 561, 1105, 1729, 2465, 2821,...
En 1912, Robert Carmichaël découvrit 15 nombres de ce type, et il conjectura leur infinité...ce qui fut démontré en 1992 : il existe au moins $n^\frac{2}{7}$ nombres de Carmichaël inférieurs à $n$.
Si le sujet vous intéresse, et si vous voulez creuser un peu plus, vous pouvez :
On le doit à Jacques Hadamard et Jean de la Vallée Poussin. Il nous enseigne que le nombre de nombres premiers inférieur ou égal à n est approximativement $n ln(n)$.
Ainsi, si on place tous les nombres dans un gigantesque tableau, puis si l'on noircit tous les nombres premiers, les cases noircies seront de plus en plus rares vers le bas du tableau.
Un jour, le mathématicien Ulam s'ennuyait dans une conférence. Il eut l'idée d'écrire les entiers suivant une spirale :
| 7 | 6 | 5 | |
| 8 | 1 | 4 | |
| 9 | 2 | 3 | 14 |
| 10 | 11 | 12 | 13 |
puis de noircir les nombres premiers. Il remarqua alors que les cases noires s'alignaient étonnamment...
Aucune fonction polynôme P(n) ne donne que des nombres premiers, sauf dans le cas trivial où ledit polynome est constant, égal à un nombre premier.
En 1947, W. Mills étonne la communauté mathématique en établissant l'existance d'une constante A qui, insérée dans la formule $\left[ A^{3^n} \right]$ donne un nombre premier, quelle que soit la valeur de l'entier n choisi.
L'utilité de cette formule est cependant illusoire : on ne peut calculer A (la constante de Mills) qu'à la condition de connaître déjà tous les nombres premiers.
$p_n = \left[ L.10^{n^2} \right] - \left[ L.10^{(n-1)^2} \right]*10^{2n-1}$ donne le $n$ième nombre premier...pourvu qu'on les connaissent déjà tous, car ici :
$L=0,2003000050000007000000011...$
(le n-ième nombre premier est placé en position $n^2$).
Les mathématiciens Minac et Willans ont imaginé une formule qui donne tous les nombres premiers dans l'ordre et sans répétition :
$p_n = \sum_{m=1}^{2^n} \left[ \left[ \frac{n}{1+ \sum_{j=1}^m \left[ \frac{(j-1)!+1}{j}-\frac{(j-1)!}{j} \right] }\right]^{\frac{1}{n}} \right]$
On ignorait qu'une telle formule puisse exister avant sa publication en 1995 (on était même pas loin d'être persuadé du contraire).
Cependant, la mise en œuvre d'une telle formule est si couteuse, qu'elle en est définitivement inexploitable.
Définition : Le pième nombre de Fermat est $F_p = 2^{2^p}+1$.
Seuls les $F_p$ qui sont premiers nous intéressent :
Ces nombres sont à rapprocher des nombres de Mersenne, avec qui Pierre de Fermat correspondait.
Pierre de Fermat pensait que tous ces nombres $F_n$ étaient premiers. Or $F_5 = 2^{2^5}+1$ , qui a dix chiffres, est divisible par 641.
Depuis, on n'a pas trouvé d'autres nombres de Fermat premiers, et on pense que seuls $F_0, F_1, F_2, F_3$ et $F_4$ le sont.
Gauss montra, dans Disquisitiones Arithmeticae, que si le $n$ième nombre de Fermat $F_n$ est premier, alors on peut construire à la règle et au compas le polygône régulier à n côtés.
On demande de programmer un algorithme permettant de générer la liste des nombres de Fermat, et de déterminer lesquels sont premiers.
Si le sujet vous intéresse, vous pouvez vous renseigner sur les polygônes constructibles à la règle et au compas.
Définition : Le $p$ième nombre de Mersenne est $M_p = 2^p-1$.
Seuls les $M_p$ qui sont premiers nous intéressent :
On en connaît un peu plus d'une quarantaine, le dernier étant le plus grand des nombres premiers connus : $2^{32582657}-1$
On les connaît depuis l'antiquité. Historiquement, on s'intéressa aux nombres premiers de Mersenne du fait de leur lien avec les nombres parfaits.
Maintenant, ils sont utilisés pour obtenir des records (plus grand nombre premier connu). Un projet (GIMPS, Great Internet Mersenne Prime Search) se consacre d'ailleurs uniquement à cette tâche.
Théorème : Pour que $M_p$ soit premier, il faut que $p$ le soit.
Cette condition n'est cependant pas suffisante : $2^{11}-1 = 23 \times 89$
$M_p$ s'écrit $1111...111$ ($p$ fois) en base 2.
Comme il faut que $p$ soit premier pour que $M_p$ le soit, on en déduit, on en déduit que les nombres premiers de Mersenne s'écrivent, en base 2, sous la forme d'un nombre premier de uns :
Edouard Lucas, en 1878, a remarqué que $M_p \textrm{ est premier} \Longleftrightarrow M_p | S_{p-2}$ ce qui donnerait une méthode relativement efficace pour savoir si $M_p$ est premier.
