Nombres premiers
Cours
1. Définition
Un entier $p \geq 2$ est premier s'il n'admet que deux diviseurs positifs : $1$ et lui-même.
2. Crible d'Ératosthène
Méthode pour lister tous les nombres premiers inférieurs à $N$ : on écrit tous les entiers de $2$ à $N$, puis on raye successivement les multiples de chaque nombre premier rencontré (en commençant par $2$).
3. Décomposition en facteurs premiers
Théorème fondamental de l'arithmétique : tout entier $n \geq 2$ se décompose de manière unique (à l'ordre près) en produit de facteurs premiers :
$$n = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \cdots \times p_k^{\alpha_k}$$
Le nombre de diviseurs positifs de $n$ est alors $(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_k+1)$.
4. Test de primalité
Pour savoir si $n$ est premier, il suffit de tester ses diviseurs jusqu'à $\sqrt{n}$ : si aucun nombre premier inférieur ou égal à $\sqrt{n}$ ne divise $n$, alors $n$ est premier.
5. Petit théorème de Fermat
Si $p$ est premier et si $a$ n'est pas divisible par $p$, alors :
$$a^{p-1} \equiv 1 \ [p]$$
Exemple
Avec $p=11$ et $a=2$ : $2^{10} \equiv 1 \ [11]$.
6. Infinité des nombres premiers
Il existe une infinité de nombres premiers (démonstration par l'absurde due à Euclide : si l'ensemble était fini, le produit de tous plus 1 fournirait un nombre premier non présent dans la liste).