Nombres premiers en Terminale maths expertes

Nombres premiers en Maths expertes : cours complet

Les nombres premiers sont les briques élémentaires des entiers : tout entier $\ge 2$≥ 2 se décompose de manière unique en produit de premiers. Ils sont au cœur de l'arithmétique et de la cryptographie moderne.

Définition

Définition

Un entier $n\ge 2$n ≥ 2 est premier s'il n'a que deux diviseurs positifs : $1$1 et $n$n.

Exemples

$$2,3,5,7,11,13,17,19,23,29,31,\dots$$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, …

Cas particulier

• $1$1 n'est pas premier (un seul diviseur).
• $2$2 est le seul premier pair.

Test de primalité

Méthode des divisions

Pour vérifier si $n$n est premier, on teste sa divisibilité par tous les premiers $p\le \sqrt{n}$p ≤ √(n).

Justification

Si $n=ab$n = ab avec $1<a\le b<n$1 < a ≤ b < n, alors $a\le \sqrt{n}$a ≤ √(n).

Exemple

$97$97 premier ? $\sqrt{97}\approx 9,8$√(97) ≈ 9,8. On teste $2,3,5,7$2, 3, 5, 7 : aucun ne divise $97$97. Donc $97$97 est premier.

Crible d'Ératosthène

Algorithme pour trouver tous les premiers $\le N$≤ N :

1. Liste tous les entiers de $2$2 à $N$N.
2. Marque le premier non marqué (premier).
3. Élimine tous ses multiples.
4. Recommence avec le suivant.

def crible(N):
    premiers = [True] * (N + 1)
    premiers[0] = premiers[1] = False
    for i in range(2, int(N**0.5) + 1):
        if premiers[i]:
            for j in range(i*i, N + 1, i):
                premiers[j] = False
    return [i for i, p in enumerate(premiers) if p]

Décomposition en facteurs premiers

Théorème fondamental de l'arithmétique

Tout entier $n\ge 2$n ≥ 2 se décompose de manière unique (à l'ordre près) en produit de premiers :

$$n=p_1^{{\alpha }_1}\times p_2^{{\alpha }_2}\times \cdots \times p_k^{{\alpha }_k}$$n = p₁^(α₁) × p₂^(α₂) × … × pₖ^(αₖ)

Exemple

$$360=2^3\times 3^2\times 5$$360 = 2³ × 3² × 5

Méthode

Diviser successivement par les premiers : $2$2, puis $3$3, $5$5, $7$7, …

Nombre de diviseurs

Si $n=p_1^{{\alpha }_1}\cdots p_k^{{\alpha }_k}$n = p₁^(α₁) … pₖ^(αₖ), le nombre de diviseurs positifs de $n$n est :

$$d(n)=({\alpha }_1+1)({\alpha }_2+1)\cdots ({\alpha }_k+1)$$d(n) = (α₁ + 1)(α₂ + 1) … (αₖ + 1)

Exemple

$360=2^3\times 3^2\times 5$360 = 2³ × 3² × 5 : $d(360)=4\times 3\times 2=24$d(360) = 4 × 3 × 2 = 24 diviseurs.

Infinité des nombres premiers

Théorème d'Euclide

Il existe une infinité de nombres premiers.

Démonstration

Par l'absurde : si $\{p_1,\dots ,p_n\}${p₁, …, pₙ} sont tous les premiers, on considère $N=p_1\cdots p_n+1$N = p₁ … pₙ + 1. $N$N n'est divisible par aucun $p_i$pᵢ, contradiction.

Petit théorème de Fermat

Énoncé

Si $p$p est premier et $\gcd (a,p)=1$gcd(a, p) = 1 :

$$a^{p-1}\equiv 1(\mathrm{mod}p)$$a^(p-1) ≡ 1 pmodp

Conséquence

$$a^p\equiv a(\mathrm{mod}p)\forall a\in \mathbb{Z}$$a^(p) ≡ a pmodp ∀ a ∈ ℤ

Application : test de primalité de Fermat

Si $p$p est premier et $a^{p-1}\not\equiv 1(\mathrm{mod}p)$a^(p-1) not≡ 1 pmodp pour un certain $a$a, alors $p$p n'est pas premier.

Attention : la réciproque est fausse (nombres de Carmichael).

Lemme de Gauss

$$p\text{ premier et }p|ab⟹p|a\text{ ou }p|b$$p premier et p | ab ⇒ p | a ou p | b

C'est ce qui fait l'unicité de la décomposition en facteurs premiers.

PGCD et PPCM via la décomposition

Si $a=\prod p_i^{{\alpha }_i}$a = Π pᵢ^(αᵢ) et $b=\prod p_i^{{\beta }_i}$b = Π pᵢ^(βᵢ) :

$$\gcd (a,b)=\prod p_i^{\min ({\alpha }_i,{\beta }_i)}$$gcd(a, b) = Π pᵢ^(min(αᵢ, βᵢ))

$$\text{ppcm}(a,b)=\prod p_i^{\max ({\alpha }_i,{\beta }_i)}$$ppcm (a, b) = Π pᵢ^(max(αᵢ, βᵢ))

Exemple

$\gcd (360,84)=\gcd (2^3\times 3^2\times 5,2^2\times 3\times 7)=2^2\times 3=12$gcd(360, 84) = gcd(2³ × 3² × 5, 2² × 3 × 7) = 2² × 3 = 12.

Applications

Cryptographie RSA

Repose sur le fait qu'il est facile de multiplier deux grands nombres premiers, mais difficile de retrouver les facteurs.

Théorie des codes

Codes correcteurs d'erreurs, codes de hachage…

Erreurs fréquentes à éviter

• Croire que $1$1 est premier.
• Mauvaise décomposition : vérifier en multipliant.
• Tester tous les entiers au lieu des seuls premiers $\le \sqrt{n}$≤ √(n) (inefficace).
• Confondre premier et impair : $2$2 est premier et pair.

FAQ — Nombres premiers

Combien de nombres premiers connaît-on ?

Une infinité (Euclide), mais on découvre régulièrement des records (le plus grand connu a des dizaines de millions de chiffres).

Pourquoi sont-ils importants ?

Ils sont les atomes des entiers : tout entier se construit à partir d'eux. Et leur rareté sert la cryptographie.

Comment trouver de très grands premiers ?

Tests probabilistes (Fermat, Miller-Rabin), suivis de tests déterministes (AKS).

À quoi sert RSA ?

À chiffrer des messages : la sécurité d'Internet (HTTPS, signatures) repose sur la difficulté de factoriser de grands entiers.