Définition

Un entier $p \geq 2$ est premier s’il n’admet que deux diviseurs positifs : $1$ et $p$ .

Premiers jusqu’à 50 : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

$1$ n’est pas premier par convention.

Crible d’Ératosthène

Pour trouver tous les premiers jusqu’à $n$ :

Lister les entiers de 2 à $n$
Pour chaque premier $p$ trouvé, éliminer ses multiples $p^2, p(p+1), \ldots$
Les nombres restants sont premiers

Astuce : On n’a besoin de tester les facteurs que jusqu’à $\sqrt{n}$ .

Décomposition en facteurs premiers

Théorème fondamental : Tout entier $n \geq 2$ se décompose de manière unique en produit de facteurs premiers :

$n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} \quad (p_1 < p_2 < \cdots < p_k)$

Exemples : $360 = 2^3 \times 3^2 \times 5$ , $1001 = 7 \times 11 \times 13$

PGCD et PPCM depuis la décomposition :

$\text{PGCD}(a,b) = \prod p_i^{\min(a_i,b_i)} \qquad \text{PPCM}(a,b) = \prod p_i^{\max(a_i,b_i)}$

Infinité des nombres premiers

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

Preuve : Supposons qu’il n’en existe qu’un nombre fini $p_1, \ldots, p_k$ . Posons $N = p_1 p_2 \cdots p_k + 1$ . Aucun $p_i$ ne divise $N$ (reste 1 dans chaque division). Donc $N$ admet un diviseur premier différent de tous les $p_i$ : contradiction.

Petit théorème de Fermat

Si $p$ est premier et $\text{PGCD}(a,p) = 1$ :

$a^{p-1} \equiv 1 \pmod{p}$

Corollaire : $a^p \equiv a \pmod{p}$ pour tout $a$ .

Application — test de primalité : Si $2^{n-1} \not\equiv 1 \pmod{n}$ , alors $n$ n’est pas premier.

Nombre de diviseurs

Si $n = p_1^{a_1} \cdots p_k^{a_k}$ , le nombre de diviseurs de $n$ est :

$\tau(n) = (a_1+1)(a_2+1)\cdots(a_k+1)$

Exemple : $360 = 2^3 \times 3^2 \times 5^1$ → $\tau(360) = 4 \times 3 \times 2 = 24$ diviseurs.