Nombres premiers

Un entier $p \geq 2$ est premier s'il n'admet que deux diviseurs positifs : 1 et lui-même.

Un entier $n \geq 2$ non premier est composé : il admet un diviseur $d$ avec $1 < d < n$.

Remarques importantes :

• 1 n'est pas premier (par convention — pour que la décomposition soit unique)
• 2 est le seul nombre premier pair
• Pour vérifier si $n$ est premier, il suffit de tester les diviseurs jusqu'à $\sqrt{n}$

Premiers nombres premiers : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, ...

Le crible d'Ératosthène trouve tous les nombres premiers jusqu'à $N$ :

1. Lister tous les entiers de 2 à $N$
2. Commencer avec $p = 2$
3. Biffer tous les multiples de $p$ supérieurs à $p$ (i.e., $2p, 3p, 4p, \ldots$)
4. Prendre le plus petit entier non biffé et répéter
5. Arrêter quand $p > \sqrt{N}$

Les entiers non biffés sont les nombres premiers jusqu'à $N$.

Complexité : $O(N \log \log N)$ — très efficace en pratique.

Théorème d'Euclide : Il existe une infinité de nombres premiers.

Preuve par l'absurde :

Supposons qu'il n'existe qu'un nombre fini de premiers $p_1, p_2, \ldots, p_k$.

Posons $N = p_1 \times p_2 \times \cdots \times p_k + 1$.

• $N > 1$, donc $N$ admet un diviseur premier $q$.
• $q$ divise $N$ et $q$ divise $p_1 \cdots p_k$ (car $q$ est l'un des $p_i$).
• Donc $q$ divise $N - p_1 \cdots p_k = 1$.
• Impossible car $q \geq 2$. Contradiction. $\square$

Note : $N$ lui-même n'est pas nécessairement premier — la preuve ne le prétend pas.

Théorème fondamental de l'arithmétique : Tout entier $n \geq 2$ s'écrit de façon unique (à l'ordre près des facteurs) comme produit de nombres premiers :

$n = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}$

avec $p_1 < p_2 < \cdots < p_k$ premiers et $a_i \geq 1$.

Lemme d'Euclide (nécessaire pour l'unicité) : Si $p$ est premier et $p \mid ab$, alors $p \mid a$ ou $p \mid b$.

Applications :

• $\gcd(a,b)$ = produit des facteurs premiers communs avec les plus petits exposants
• $\text{ppcm}(a,b)$ = produit des facteurs premiers (de $a$ ou $b$) avec les plus grands exposants

Petit théorème de Fermat : Si $p$ est premier et $\gcd(a, p) = 1$, alors : $a^{p-1} \equiv 1 \pmod{p}$

Équivalent pour tout entier $a$ : $a^p \equiv a \pmod{p}$.

Applications :

• Calculer de grandes puissances modulo $p$ (cryptographie, RSA)
• Test de primalité de Fermat : si $a^{n-1} \not\equiv 1 \pmod{n}$ pour un certain $a$ avec $\gcd(a,n)=1$, alors $n$ est composé

Attention — réciproque fausse : les nombres de Carmichael (ex. $561 = 3\times 11\times 17$) vérifient $a^{n-1} \equiv 1 \pmod{n}$ pour tout $a$ copremier avec $n$, sans être premiers. Le petit théorème est une condition nécessaire, pas suffisante.

Test de Miller-Rabin : version probabiliste robuste utilisée en pratique (OpenSSL, Python sympy.isprime). Si $n$ passe $k$ rondes de Miller-Rabin, la probabilité qu'il soit composé est $< 4^{-k}$.