Médaille
N°1 pour apprendre & réviser du collège au lycée.
Nombres premiers

Déjà plus de

1 million

d'inscrits !

Introduction :

Ce cours sur les nombres premiers débute par les définitions et propriétés permettant de comprendre cette notion. Nous verrons ensuite les critères de divisibilité qui aideront à reconnaitre ces nombres premiers. Nous terminerons ce cours en voyant la décomposition en produit de facteurs.

Définitions et propriétés des nombres premiers

Définitions

bannière astuce

Astuce

Par convention, dans ce cours nous n’utiliserons que des nombres dont les diviseurs et les multiples sont des entiers naturels.

bannière definition

Définition

Nombre premier :

Un nombre entier est dit premier s’il admet exactement deux diviseurs positifs : 1 et lui-même.

bannière exemple

Exemple

Les nombres 22, 33 et 55 sont des nombres premiers. Le nombre 88 n’est pas un nombre premier car il est divisible par 11, 22, 44 et 88.

L’entier naturel 11 n’est pas un nombre premier car il n’admet qu’un seul diviseur positif : 11.

Propriétés

bannière propriete

Propriété

Tout nombre entier aa strictement supérieur à 11 admet un diviseur premier.

bannière demonstration

Démonstration

Si aa est premier, alors le diviseur premier cherché est aa.

Si aa n’est pas premier, alors, par définition, il admet au moins un diviseur strict. Notons D(a)\text D(a) l’ensemble de ses diviseurs de aa ; D(a)={1 ; d1 ; d2 ;  ; a}\text D(a)=\lbrace 1\ ;\ d1\ ;\ d2\ ;\ …\ ;\ a\rbrace avec 1<d1<d2<<a1 < d1 < d2 < … < a.

Prouvons par l’absurde que le plus petit diviseur strict de aa, soit d1d_1, est un nombre premier.

Supposons donc que d1d1 est non premier. Alors d1d1 admet au moins un diviseur strict dd : 1<d<d11 < d < d_1.

Il en résulterait que dd divise d1d1, et d1d1 divise a donc dd est un diviseur strict de aa strictement inférieur à d1d_1 ce qui est impossible.

  • Donc d1d_1 est premier.
bannière propriete

Propriété

Tout nombre entier aa non premier et strictement supérieur à 11 admet un diviseur strict inférieur ou égal à a\sqrt a.

bannière demonstration

Démonstration

Soit aa un entier non premier strictement supérieur à 11 ; on appelle dd le plus petit diviseur de aa tel que 1<d<a1 < d < a.

D’après la propriété précédente, dd est un nombre premier. De plus, il existe un entier kk tel que n=d×kn=d\times k.

Ainsi, kk est un diviseur de aa supérieur ou égal à dd d’où n=d×kd×dn=d\times k ≥d\times d.

nd2n≥d^2 donc nd\sqrt n≥d.

bannière à retenir

À retenir

Ce résultat est utile lorsqu’on veut prouver qu’un nombre aa est premier : il suffit de vérifier qu’il n’a pas de diviseur strict inférieur ou égal à a\sqrt a.

bannière propriete

Propriété

Il existe une infinité de nombres premiers.

On pourra remarquer qu’ainsi, il n’existe pas de « plus grand nombre premier » : pour tout nombre premier pp, il existe un nombre premier qq strictement supérieur à pp.

Ce théorème se démontre par l’absurde. Supposons donc qu’il n’existe qu’un nombre fini de nombres premiers : 2<3<5<<p2 < 3 < 5 < … < p.

Posons N=(2×3××p)+1\text N=(2\times3\times…\times p)+1. Le nombre N\text N est strictement supérieur à 11. Il admet donc un diviseur premier dd.

Comme les nombres 22, 33, 55 jusqu’à pp sont les seuls nombres premiers, dd est nécessairement l’un de ces nombres. Le nombre dd divise donc le produit 2×3×4×52\times3\times4\times5 et ainsi de suite jusqu’à pp.

Mais dd divise également le nombre N\text N : il divise donc leur différence 11, ce qui est impossible. Il existe donc une infinité de nombres premiers.

Critères de divisibilité en base 10

Soit le nombre n=xpxp1x1x010n=\overline{xpx{p-1}…x1x0}^{10} dans nn, x0 x0 est le chiffre des unités, x1x1 le chiffre des dizaines, etc.

Critère de divisibilité par 2

On a n=xpxp1x1×10+x0n=\overline{xpx{p-1}…x1}\times10+x0 or 100 [2]10≡0\ [2] donc nx0 [2]n≡x_0\ [2].

bannière propriete

Propriété

Il en résulte que nn est divisible par 22 si, et seulement si, son chiffre des unités est divisible par 22, c’est-à-dire s’il se termine par 00, 22, 44, 66 ou 88.

Critère de divisibilité par 3

On a n=xp10p+xp110p1++x1101+x0n=xp10^p+x{p-1}10^{p-1}+…+x110^1+x0 or 101 [3]10≡1\ [3] donc, pour tout entier naturel kk, 10k1 [3]10k≡1\ [3].

Ainsi, nxp+xp1++x1+x0 [3]n≡xp+x{p-1}+…+x1+x0\ [3].

bannière propriete

Propriété

Il en résulte que nn est divisible par 33 si et seulement si la somme de ses chiffres est divisible par 33.

Critère de divisibilité par 4

bannière propriete

Propriété

Un entier naturel est divisible par 44 si et seulement si le nombre formé avec ses deux derniers chiffres est divisible par 44.

Critère de divisibilité par 5

On a n=xpxp1x1×10+x0n=\overline{xpx{p-1}…x1}\times10+x0 or 100 [5]10≡0\ [5] donc nx0 [5]n≡x_0\ [5].

bannière propriete

Propriété

Il en résulte que nn est divisible par 55 si, et seulement si, son chiffre des unités est divisible par 55, c’est-à-dire s’il se termine par 00 ou 55.

Critère de divisibilité par 9

On a n=xp10p+xp110p1++x1101+x0n=xp10^p+x{p-1}10^{p-1}+…+x110^1+x0 or 101 [9]10≡1\ [9] donc, pour tout entier kk, 10k1k [9]10^k≡1^k\ [9] soit 10k1 [9]10^k≡1\ [9]. Ainsi, nxp+xp1++x1+x0 [9]n≡xp+x{p-1}+…+x1+x0\ [9].

bannière propriete

Propriété

Il en résulte que nn est divisible par 99 si et seulement si la somme de ses chiffres est divisible par 99.

Critère de divisibilité par 10

On a n=xpxp1x1×10+x0n=\overline{xpx{p-1}…x1}\times10+x0 donc nx0n-x0 est divisible par 1010 donc nx0 [10]n≡x0\ [10].

bannière propriete

Propriété

Il en résulte que nn est divisible par 1010 si, et seulement si, son chiffre des unités est divisible par 1010, c’est-à-dire s’il se termine par 00.

Déterminer si un nombre donné est premier

Pour savoir si un nombre est premier, nous pouvons utiliser la contraposée de la proposition « Tout nombre entier aa non premier et strictement supérieur à 11 admet un diviseur strict inférieur ou égal à a\sqrt a ».

bannière propriete

Propriété

Si aa n’admet pas de diviseur premier strict inférieur ou égal à a\sqrt a, alors aa est premier.

bannière exemple

Exemple

36719,2\sqrt{367}≈19,2

Les nombres premiers inférieurs à 367\sqrt{367} sont 2,3,5,7,11,13,17 et 192, 3, 5, 7, 11, 13, 17\text{ et }19.

  • Le nombre 22 ne divise pas 367367 qui est un nombre impair.
  • 33 ne divise pas 367367 car 33 ne divise pas la somme de ses chiffres : 3+6+7=163+6+7=16 et 1+6=71+6=7 non divisible par 33
  • 55 ne divise pas 367367
  • 367=7×52+3367=7\times52+3 donc 77 ne divise pas 367367
  • 367=11×33+4367=11\times33+4 donc 1111 ne divise pas 367367
  • 367=13×28+3367=13\times28+3 donc 1313 ne divise pas 367367
  • 367=17×21+10367=17\times21+10 donc 1717 ne divise pas 367367
  • 367=19×19+6367=19\times19+6 donc 1919 ne divise pas 367367

Il n’existe aucun nombre premier inférieur à 367\sqrt{367} qui soit un diviseur de 367367 donc 367367 est un nombre premier.

Décomposition en produit de facteurs

bannière propriete

Propriété

Un nombre entier naturel strictement supérieur à 11 est premier ou se décompose de manière unique, à l’ordre près, en produit de nombres premiers.

bannière demonstration

Démonstration

nn est un entier naturel non premier. Il admet alors un diviseur strict premier p1p1. Donc n=p1×q1n=p1\times q1q1q1 est aussi un diviseur strict de nn (sinon p1=1p1=1 ou p1=np1=n, ce qui est impossible). Ainsi q1q_1 est strictement inférieur à l’entier nn.

  • Si q1q1 est premier, alors nn est le produit de deux nombres premiers : n=p1×q1n=p1\times q_1
  • Si q1q1 n’est pas premier, alors il admet un diviseur strict premier p2p2. Donc q1=p2×q2q1=p2\times q2p2p2 est un diviseur strict de q1q1. Ainsi q2<q1<nq2 < q_1 < n.
  • Si p2p2 est premier, nn est le produit de trois nombres premiers n=p1×p2×q2n=p1\times p2\times q2

Tant que qiqi n’est pas premier, on réitère ce processus. On construit ainsi une suite d’entiers naturels 1qi<qi1<<q3<q2<q11 ≤ qi < q{i-1} < … < q3 < q2 < q1.

Comme cette suite est finie, ce processus doit s’arrêter : il existe donc un diviseur qkq_k premier.

Ainsi, nn est le produit de facteurs premiers n=p1×p2××pk×qkn=p1\times p2\times …\times pk\times qk.

L’unicité de la décomposition est admise.

bannière propriete

Propriété

nn est un entier naturel non premier dont la décomposition en produit de facteurs premiers est : p1α1p2α2pkαkp1^{α1}p2^{α2}…pk^{αk}

Alors les diviseurs de nn sont tous les nombres qui s’écrivent p1β1p2β2...pkβkp1^{β1}p2^{β2}…pk^{βk}avec 0β1α10≤β1≤α1, 0β2α20≤β2≤α2, …, 0βkαk0≤βk≤αk.

bannière exemple

Exemple

n=2×35×52n=2\times35\times52. Ses diviseurs sont tous les nombres 2×3β×5γ2^∝\times3^β\times5^\gamma obtenus en prenant α\alpha dans l’ensemble {0 ;1}\lbrace 0\ ;1\rbrace , ββ dans {0 ;1 ;2 ;3}\lbrace0\ ;1\ ;2\ ;3\rbrace et γγ dans {0 ;1 ;2}\lbrace0\ ;1\ ;2\rbrace.

Le nombre de diviseurs est le nombre de choix possibles de la liste α\alpha, β\beta, γ\gamma. Il y a donc 2424 diviseurs dans l’exemple précédent car 2×4×3=242\times4\times3=24 (deux choix pour α\alpha, quatre choix pour β\beta et trois choix pour γ\gamma).

D’une manière générale, si la décomposition en produit de facteurs premiers d’un entier naturel nn est n=p1α1p2α2pkαkn=p1^{α1}p2^{α2}…pk^{αk}, alors le nombre nn admet (α1+1)(α2+1)(αk+1)1+1)(α2+1)…(αk+1) diviseurs.