ℙ

Fiche de révision Maths expertes

Nombres premiers

Chapitre 23 — les briques élémentaires de l'arithmétique : test de primalité, théorèmes d'Euclide et de Fermat, et la factorisation des entiers.

Euclide a prouvé qu'ils sont en nombre infini ; la conjecture de Goldbach, elle, résiste encore.

Naviguez avec les flèches ← → du clavier, ou via le Sommaire.

Chapitre 23 Vue d'ensemble

Au programme

Partie 1 — Propriétés

Définition et test de primalité
Une infinité de nombres premiers
Lemme d'Euclide et théorème de Fermat

Partie 2 — Factorisation

Le théorème fondamental de l'arithmétique
Compter les diviseurs d'un entier
Calculer un pgcd par factorisation

Deux outils puissants

Le lemme d'Euclide ($p\mid ab\Rightarrow p\mid a$ ou $p\mid b$) et le petit théorème de Fermat ($n^p\equiv n\ [p]$) reviennent sans cesse.

Partie 1 Le point de départ

Qu'est-ce qu'un nombre premier ?

Définition

Un entier $p$ est premier lorsqu'il admet exactement deux diviseurs positifs : $1$ et lui-même.

$$p \text{ premier} \iff \operatorname{Div}(p)\cap\mathbb{N}=\{1,\,p\}$$

À retenir

$1$ n'est pas premier (un seul diviseur), $0$ non plus.
$2$ est le seul nombre premier pair.
Un entier $\geqslant 2$ non premier est dit composé.

Partie 1 ★ Savoir-faire

Tester si un nombre est premier

Le résultat clé

Tout entier $n\geqslant 2$ composé admet un plus petit diviseur premier $p$ tel que $p^2\leqslant n$. Par contraposée :

$$\text{aucun premier } p\leqslant\sqrt{n} \text{ ne divise } n \ \implies\ n \text{ est premier}$$

En pratique : il suffit de tester les diviseurs jusqu'à $\sqrt{n}$.

def est_premier(n):
    if n < 2: return False
    if n % 2 == 0: return n == 2
    d = 3
    while d*d <= n:
        if n % d == 0: return False
        d += 2
    return True

Partie 1 Un résultat d'Euclide

Ils sont en nombre infini

Théorème

L'ensemble $\mathbb{P}$ des nombres premiers est infini.

L'idée de la preuve (par l'absurde)

S'il y en avait un nombre fini $2,3,5,\dots,p$, on pose $N=2\times 3\times\cdots\times p$ et $N'=N+1$. Tout diviseur premier $q$ de $N'$ diviserait aussi $N$, donc $q\mid 1$ : impossible.

Partie 1 ★ Outil majeur

Le lemme d'Euclide

Premier théorème d'Euclide

Si $p$ est premier et $p\mid ab$, alors :

$$p\mid a \quad\text{ou}\quad p\mid b$$

En particulier $p\mid a^n \implies p\mid a$. (Faux si $p$ n'est pas premier : $6\mid 4\times 9$ mais $6\nmid 4$ et $6\nmid 9$.)

Pourquoi

Si $p\nmid a$, alors $p$ et $a$ sont premiers entre eux : le théorème de Gauss donne alors $p\mid b$.

Partie 1 Savoir-faire

Résoudre un second degré modulo $p$

Méthode — $x^2+x+7\equiv 0\ [13]$

On repère une solution évidente : $x\equiv 2$ convient.
On factorise : l'équation devient $(x-2)(x+3)\equiv 0\ [13]$.
$13$ premier $\Rightarrow$ lemme d'Euclide : $x-2\equiv 0$ ou $x+3\equiv 0$.

D'où $x\equiv 2\ [13]$ ou $x\equiv -3\equiv 10\ [13]$.

Le réflexe

Modulo un nombre premier, un produit nul $\Rightarrow$ un des facteurs est nul : c'est ce qui permet de factoriser et de conclure.

Partie 1 ★ Théorème majeur

Le petit théorème de Fermat

Théorème

Pour $p$ premier et tout $n\in\mathbb{Z}$ :

$$n^{p}\equiv n\ [p]$$

Et si de plus $p\nmid n$ : $\quad n^{p-1}\equiv 1\ [p].$

Attention

C'est une condition nécessaire de primalité, mais pas suffisante : certains entiers composés (nombres de Carmichaël) la vérifient aussi.

Partie 1 Savoir-faire

Utiliser Fermat

Application directe

Pour tout $n$ : $\ p\mid n^{p}-n$. Par exemple $7\mid n^{7}-n$ et $5\mid n^{5}-n$, sans calcul.

Aller plus loin — montrer $51\mid n^{17}-n$

Modulo $17$ : Fermat donne directement $n^{17}\equiv n$.
Modulo $3$ : Fermat ($n^3\equiv n$) appliqué de proche en proche donne aussi $n^{17}\equiv n$.
$3\wedge 17=1$ et tous deux divisent $n^{17}-n$, donc (Gauss) $51\mid n^{17}-n$.

Partie 2 ★ Le résultat central

Le théorème fondamental

Existence et unicité

Tout entier $n\geqslant 2$ s'écrit de manière unique (à l'ordre près) comme produit de facteurs premiers :

$$n=p_1^{\alpha_1}\times p_2^{\alpha_2}\times\cdots\times p_r^{\alpha_r},\qquad p_1\lt p_2\lt\cdots\lt p_r$$

Exemple

$4116=2^{2}\times 3\times 7^{3}$.

Partie 2 Savoir-faire

Factoriser un entier

Méthode — divisions successives

On divise par le plus petit diviseur premier, puis on recommence avec le quotient, jusqu'à atteindre $1$. Pour $4116$ : $\div2$, $\div2$, $\div3$, $\div7$, $\div7$, $\div7$.

$$4116=2^{2}\times 3\times 7^{3}$$

def factorisation(n):
    d = 2
    L = []
    while n != 1:
        while n % d == 0:
            n = n // d
            L.append(d)
        d = d + 1
    return L

Partie 2 Application

Compter les diviseurs

Caractérisation

Les diviseurs de $n=\prod p_i^{\alpha_i}$ sont exactement les $d=\prod p_i^{\beta_i}$ avec $0\leqslant\beta_i\leqslant\alpha_i$.

Nombre de diviseurs

$$\text{nombre de diviseurs de } n=\prod_{i=1}^{k}(1+\alpha_i)$$

Exemple : $N=2^{10}\times 3^{2}$ admet $(1+10)(1+2)=33$ diviseurs.

Partie 2 Application

Le pgcd par factorisation

Formule

Avec $a=\prod p_i^{\alpha_i}$ et $b=\prod p_i^{\beta_i}$ (mêmes premiers, exposants éventuellement nuls) :

$$\operatorname{pgcd}(a,b)=\prod_{i=1}^{k} p_i^{\min(\alpha_i,\,\beta_i)}$$

Exemple

$520=2^{3}\times 5\times 13$ et $156832=2^{5}\times 13^{2}\times 29$ donnent $\operatorname{pgcd}=2^{3}\times 13=104$.

Synthèse À revoir 5 min avant

Mémo express

Premier$\operatorname{Div}(p)\cap\mathbb{N}=\{1,p\}$

Testtester les diviseurs jusqu'à $\sqrt{n}$

Lemme d'Euclide$p\mid ab\Rightarrow p\mid a$ ou $p\mid b$

Fermat$n^{p}\equiv n\ [p]$ ; $n^{p-1}\equiv 1$ si $p\nmid n$

Factorisation$n=\prod p_i^{\alpha_i}$ (unique)

Diviseurs / pgcd$\prod(1+\alpha_i)$ ; $\prod p_i^{\min(\alpha_i,\beta_i)}$

Vigilance Le jour J

Les pièges à éviter

Piège

$1$ n'est pas premier ; $2$ est le seul premier pair.
$p\mid ab\Rightarrow p\mid a$ ou $p\mid b$ n'est vrai que si $p$ est premier.
Fermat est une condition nécessaire, non suffisante (Carmichaël).
Pour tester la primalité, inutile d'aller au-delà de $\sqrt{n}$.

Auto-évaluation Cliquez pour la réponse

Quiz éclair

Q1$1$ est-il un nombre premier ?

Non : il n'a qu'un seul diviseur positif.

▸ cliquer pour révéler

Q2Jusqu'où tester les diviseurs pour la primalité de $n$ ?

Jusqu'à $\sqrt{n}$ (un diviseur composé en cacherait un premier $\leqslant\sqrt{n}$).

▸ cliquer pour révéler

Q3Si $p$ premier et $p\mid n^{5}$, que dire de $p$ et $n$ ?

$p\mid n$ (lemme d'Euclide).

▸ cliquer pour révéler

Q4Combien de diviseurs a $n=2^{10}\times 3^{2}$ ?

$(1+10)(1+2)=33$.

▸ cliquer pour révéler