Compétence · Terminale TE.NPRE.TEST.01 Niveau : Facile

Reconnaître un nombre premier

Un nombre premier a exactement deux diviseurs ; tout entier n ≥ 2 a un diviseur premier ; tester si n est premier en essayant les nombres premiers p tels que p² ≤ n ; il existe une infinité de nombres premiers (preuve d'Euclide).

Chapitre : Nombres premiers et petit théorème de Fermat Filière : Term Maths Expertes Temps de maîtrise : ~30 min

Le cours

Nombres premiers et test de primalité~3 min

Définition — nombre premier

Un entier naturel $p$ est premier s'il possède exactement deux diviseurs positifs : $1$ et $p$. Ainsi $0$ et $1$ ne sont pas premiers ; $2$ est le seul premier pair. Un entier $n\geq2$ non premier est dit composé : $n=ab$ avec $1\lt a\leq b\lt n$.

À retenir — deux propriétés fondamentales

1. Tout entier $n\geq2$ admet au moins un diviseur premier : le plus petit diviseur $d\gt 1$ de $n$ est premier.
Preuve : si $d$ avait un diviseur $d'$ avec $1\lt d'\lt d$, alors $d'$ diviserait $n$ et contredirait la minimalité de $d$.
2. Test de primalité. Si $n\geq2$ n'est divisible par aucun nombre premier $p$ tel que $p\leq\sqrt n$, alors $n$ est premier.
Preuve : si $n=ab$ avec $1\lt a\leq b$, alors $a^2\leq ab=n$, donc $a\leq\sqrt n$, et le plus petit diviseur premier de $a$ est un diviseur premier de $n$ inférieur ou égal à $\sqrt n$.

Méthode — tester si $n$ est premier

1. Encadrer $\sqrt n$ : trouver le plus grand premier $p\leq\sqrt n$.
2. Tester la divisibilité de $n$ par $2,3,5,7,11,\dots,p$ (critères ou division).
3. Aucun ne divise $n$ : $n$ est premier. Sinon on a un diviseur, $n$ est composé.

Exemple

Exemple : $n=191$ : $13^2=169\leq191\lt 196=14^2$, donc $\sqrt{191}\lt 14$ ; premiers à tester : $2,3,5,7,11,13$.
$191$ impair ; $1+9+1=11$ non multiple de $3$ ; ne finit ni par $0$ ni par $5$ ; $191=7\times27+2$ ; $191=11\times17+4$ ; $191=13\times14+9$. $191$ est premier.

Exemple : $n=221$ : $\sqrt{221}\lt 15$ ; $2,3,5,7,11$ ne divisent pas $221$ mais $221=13\times17$ : composé.

Crible d'Ératosthène jusqu'à $50$ : on barre les multiples de $2,3,5,7$ ($7\leq\sqrt{50}\lt 8$ suffit) ; il reste les $15$ nombres premiers inférieurs à $50$.

Avec Python — test de primalité et crible d'Ératosthène
def est_premier(n):
    if n < 2:
        return False
    d = 2
    while d * d <= n:     # d <= racine de n
        if n % d == 0:
            return False
        d = d + 1
    return True
def crible(N):
    premier = [True] * (N + 1)   # indices 0..N
    premier[0] = premier[1] = False
    for p in range(2, N + 1):
        if premier[p]:           # p est premier :
            for m in range(p * p, N + 1, p):
                premier[m] = False   # on barre ses multiples
    return [p for p in range(N + 1) if premier[p]]

crible(50) renvoie [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]. On commence à barrer à $p^2$ : les multiples plus petits ont déjà été barrés par un premier plus petit.

À retenir — il existe une infinité de nombres premiers

L'ensemble des nombres premiers est infini.

Démonstration exigible — infinitude des nombres premiers (Euclide)

Raisonnons par l'absurde : supposons qu'il n'y ait qu'un nombre fini de nombres premiers, $p_1,p_2,\dots,p_k$. Posons $N=p_1p_2\cdots p_k+1$.
$N\geq2$, donc $N$ admet un diviseur premier $q$ (propriété 1). Par hypothèse, $q$ est l'un des $p_i$ : $q$ divise donc le produit $p_1p_2\cdots p_k$. Comme $q$ divise aussi $N$, $q$ divise la différence $N-p_1p_2\cdots p_k=1$ : impossible pour un nombre premier ($q\geq2$).
Contradiction : il y a une infinité de nombres premiers.
Attention : $N$ n'est pas forcément premier ($2\times3\times5\times7\times11\times13+1=30031=59\times509$) ; on utilise seulement qu'il a un diviseur premier.

Conçu et validé par Laurent Jacquet, professeur de mathématiques. Qui conçoit les cours ?

Entraîne-toi sur ce cours

Avec un compte gratuit : les QCM et ta Konfiance après chaque question, et le sentier complet d'un chapitre au choix, rappels et épreuve compris.

S'inscrire gratuitement

Déjà inscrit ? Se connecter

Pour aller plus loin

Maîtrise cette compétence avec Konfia

Tous les sentiers, tous les corrigés détaillés et les rappels de révision : 29 € l'année, ou 4,99 € par mois.

Voir l'abonnement