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

Nombres premiers et petit théorème de Fermat

Déjà plus de

1 million

d'inscrits !

Avant de commencer, regarde la vidéo

Introduction :

Dans l’ensemble N\mathbb N, une place particulière est faite, depuis l’Antiquité, à l’étude des nombres premiers. Ces nombres, qui d’après leur définition ne sont divisibles que par 11 et eux-mêmes, permettent d’obtenir par multiplication tous les nombres entiers.
De nos jours, une grande part de la recherche mathématique s’intéresse à eux, à leur obtention et à leur utilisation, notamment dans le numérique et le codage des données.

Dans une première partie, nous définirons les nombres premiers, et nous apprendrons comment reconnaître qu’un nombre est premier ou non.
Nous verrons, dans une deuxième partie, que tout nombre entier peut être « généré » à partir de nombres premiers.
Dans la dernière partie de ce cours, nous nous intéresserons à un résultat de l’arithmétique, le petit théorème de Fermat, qui a de nombreuses applications.

  • Dans tout ce chapitre, nous travaillerons dans l’ensemble N\mathbb N.

Nombres premiers

Nous avons déjà abordé les nombres premiers en classe de seconde ; nous allons rappeler les définitions et les premières propriétés de ces nombres.

Définition et exemples

bannière definition

Définition

Nombre premier :

Soit nNn\in\mathbb N.
nn est un nombre premier lorsqu’il a exactement deux diviseurs entiers naturels distincts : 11 et lui-même.

bannière exemple

Exemple

  • 1313 est un nombre premier ; en effet, ses seuls diviseurs sont 11 et 1313.
  • L’ensemble des diviseurs positifs de 3535 est : D(35)={1,5,7,35}\text{D}(35)=\lbrace 1,\,5,\,7,\,35 \rbrace : 3535 n’est pas un nombre premier.

Donnons quelques conséquences :

  • 00 n’est pas premier, car il a une infinité de diviseurs.
  • Le nombre 11 n’est pas un nombre premier, puisqu’il n’a qu’un diviseur : 11.
  • 22 est un nombre premier, car il a exactement deux diviseurs : 11 et 22.
  • Aucun nombre pair strictement supérieur à 22 n’est un nombre premier.
  • En effet, si nn est un nombre pair strictement supérieur à 22, alors il a au moins trois diviseurs : 11, 22 et nn.

Illustrons comment prouver qu’un nombre est premier ou non en recherchant la liste de ses diviseurs.

bannière exemple

Exemple

Soit nNn\in \mathbb N, avec n2n\geq 2.
Nous cherchons à savoir si le nombre entier n2+4n5n^2+4n-5 peut être un nombre premier.

bannière à retenir

À retenir

Méthodologie :

Pour montrer qu’un nombre nn n’est pas premier, il suffit de trouver un diviseur de nn différent de 11 et de lui-même.

  • Pour ce faire, on essaiera d’écrire nn comme un produit de nombres entiers.

Pour trouver d’éventuels diviseurs de n2+4n5n^2+4n-5, essayons de factoriser cette expression en utilisant la forme canonique d’un polynôme du second degré.

  • Le polynôme s’écrit sous la forme an2+bn+can^2+bn+c, avec a=1a=1, b=4b=4, c=5c=-5.

n2+4n5=an2+bn+c=(nα)2+β [ouˋ α=b2a et β=aα2+bα+c]=(n+2)2+485=(n+2)29=(n+2)232=(n+2+3)(n+23)=(n+5)(n1)\begin{aligned} n^2+4n-5&= an^2+bn+c \ &=(n-\alpha)^2+\beta \footnotesize{\textcolor{#A9A9A9}{\text{ [où $\alpha=-\frac b{2a}$ et $\beta=a\alpha^2+b\alpha+c$]}}} \ &=(n+2)^2+4-8-5 \ &=(n+2)^2-9 \ &=(n+2)^2-3^2 \ &=(n+2+3)(n+2-3) \ &=(n+5)(n-1) \end{aligned}

Comme n2n\geq 2, on a : n+5>n11n+5>n-1\geq 1.

Nous envisageons donc les deux cas suivants :

  • n1=1n-1=1, c’est-à-dire n=2n=2.
  • Dans ce cas, n2+4n5=7×1n^2+4n-5=7\times1 est un nombre premier.
  • n1>1n-1>1, c’est-à-dire n>2n>2.

Les nombres entiers (n+5)(n+5) et (n1)(n-1) sont des diviseurs de n2+4n5n^2+4n-5 et sont tous les deux strictement supérieurs à 11.

  • Dans ce cas, n2+4n5n^2+4n-5 n’est pas premier.
  • En conclusion, n2+4n5n^2+4n-5 est un nombre premier si et seulement si n=2n=2.

Dans cet exemple, nous avons déterminé si un entier pouvait être un nombre premier en recherchant ses diviseurs. Parfois, il n’est pas évident de trouver ces diviseurs.
Dans le paragraphe suivant, nous allons donc utiliser un algorithme pour déterminer si un nombre est premier.

Reconnaître si un nombre est premier

Ce critère de reconnaissance d’un nombre premier a été trouvé dans les travaux d’un mathématicien du XIIIe siècle, Léonard de Pise, connu sous le nom de Fibonacci.

bannière propriete

Propriété

Prenons nNn \in \mathbb N, avec n4n\geq4.
Si nn n’est pas un nombre premier, alors nn admet au moins un diviseur premier pp tel que 2pn2\leq p\leq \sqrt{n}.

Nous allons démontrer cette propriété.

bannière demonstration

Démonstration

Soit n4n\geq 4, un nombre entier qui n’est pas premier.

  • L’ensemble D(n)\text D(n) n’est pas vide, donc il admet un plus petit élément : notons alors pp le plus petit diviseur de nn tel que :

{pnp2\begin{cases} p\neq n \ p\geq2 \end{cases}

  • Supposons par l’absurde que pp n’est pas premier : il a lui-même un diviseur dd différent de 11 et de pp selon la définition d’un nombre premier.

pp a donc un diviseur dd tel que 2d<p2\leq d.
Comme dd divise pp et pp divise nn, alors, par transitivité, dd divise nn.

dd est donc un diviseur de nn plus petit que pp et supérieur à 22, ce qui contredit la définition de pp.

  • pp est donc premier.
  • pp divise nn, donc il existe qNq\in \mathbb N tel que : n=pqn=p q, avec pqp\leq q. Ainsi :

p×pp×qSoit : p2nOn en deˊduit : pn\begin{aligned} p\times p&\leq p\times q \ \textcolor{#A9A9A9}{\text{Soit\ :\ }} p^2&\leq n \ \textcolor{#A9A9A9}{\text{On en déduit\ :\ }} p&\leq \sqrt{n} \end{aligned}

bannière astuce

Astuce

Nous utiliserons souvent cette propriété dans sa forme contraposée.

bannière propriete

Propriété

Si nn n’admet aucun diviseur premier inférieur à n\sqrt n, alors nn est un nombre premier.

Prenons un exemple pour illustrer l’utilisation de cette propriété.

bannière exemple

Exemple

Nous voulons savoir si le nombre 127127 est premier.
Nous testons alors la divisibilité de 127127 par tous les nombres premiers inférieurs à 12711,3\sqrt{127}\approx 11,3.

  • En utilisant les critères de divisibilité, nous prouvons que 127127 n’est divisible ni par 22, ni par 33, ni par 55.
  • Testons la divisibilité par 77 : la division euclidienne de 127127 par 77 donne :

127=7×18+1127=7\times18+1

  • Donc 127127 n’est pas divisible par 77.
  • Testons la divisibilité par 1111 :

127=11×11+6127=11 \times11+6

  • Donc 127127 n’est pas divisible par 1111.
  • Ainsi, 127127 n’est divisible par aucun des nombres premiers inférieurs à 127\sqrt{127}.
  • En utilisant la contraposée ci-dessus, nous avons donc prouvé que 127127 est un nombre premier.

Toujours en utilisant cette propriété, nous pouvons également établir la liste des nombres premiers inférieurs à un entier nn.
Pour déterminer cette liste, on utilise le crible (ou critère) d’Ératosthène, un savant de l’Antiquité, qui a vécu au IIIe s. av. J.-C.
Sa méthode part d’un tableau où sont écrits les nn premiers nombres entiers supérieurs ou égaux à 11.

Nous allons illustrer cette méthode avec n=119n=119 et déterminer les nombres premiers compris entre 11 et 119119. Ils nous seront utiles plus tard quand nous décomposerons un nombre entier en facteurs premiers.
Nous allons mettre en gris tous les nombres entiers qui ne sont pas premiers ; et encadrer les nombres premiers au fur et à mesure que nous les trouverons.

  • Nous commençons par griser 11 et, excepté 22, tous les nombres pairs, qui ne sont pas des nombres premiers.

11 2\purple{\boxed 2} 33 44 55 66 77 88 99
1010 1111 1212 1313 1414 1515 1616 1717 1818 1919
2020 2121 2222 2323 2424 2525 2626 2727 2828 2929
3030 3131 3232 3333 3434 3535 3636 3737 3838 3939
4040 4141 4242 4343 4444 4545 4646 4747 4848 4949
5050 5151 5252 5353 5454 5555 5656 5757 5858 5959
6060 6161 6262 6363 6464 6565 6666 6767 6868 6969
7070 7171 7272 7373 7474 7575 7676 7777 7878 7979
8080 8181 8282 8383 8484 8585 8686 8787 8888 8989
9090 9191 9292 9393 9494 9595 9696 9797 9898 9999
100100 101101 102102 103103 104104 105105 106106 107107 108108 109109
110110 111111 112112 113113 114114 115115 116116 117117 118118 119119
  • Puis, nous entourons 33, qui est premier, et barrons tous les multiples de 33.

Pour les reconnaître, nous utilisons le critère de divisibilité : « Un entier est divisible par 33 si et seulement si la somme de ses chiffres est un multiple de 33 ».

  • De la même manière, nous entourons 55, qui est premier, et barrons tous les multiples de 55, c’est-à-dire ceux qui se terminent par 00 ou 55.
  • Le nombre premier suivant est 77. Nous l’entourons et barrons ensuite tous les multiples de 77.

11 2\purple{\boxed 2} 3\purple{\boxed 3} 44 5\purple{\boxed 5} 66 7\purple{\boxed 7} 88 99
1010 1111 1212 1313 1414 1515 1616 1717 1818 1919
2020 2121 2222 2323 2424 2525 2626 2727 2828 2929
3030 3131 3232 3333 3434 3535 3636 3737 3838 3939
4040 4141 4242 4343 4444 4545 4646 4747 4848 4949
5050 5151 5252 5353 5454 5555 5656 5757 5858 5959
6060 6161 6262 6363 6464 6565 6666 6767 6868 6969
7070 7171 7272 7373 7474 7575 7676 7777 7878 7979
8080 8181 8282 8383 8484 8585 8686 8787 8888 8989
9090 9191 9292 9393 9494 9595 9696 9797 9898 9999
100100 101101 102102 103103 104104 105105 106106 107107 108108 109109
110110 111111 112112 113113 114114 115115 116116 117117 118118 119119
  • En utilisant la propriété ci-dessus, nous savons que, si 4n1194\leq n\leq119 et qu’il n’est pas premier, alors il admet un diviseur premier inférieur à 11910,91\sqrt{119}\approx10,91, donc inférieur ou égal à 1010.

Nous avons grisé les multiples des nombres premiers inférieurs ou égaux à 1010 ; donc nous avons trouvé tous les nombres de la grille qui ne sont pas premiers.

  • Les nombres sur fond blanc sont donc les nombres premiers inférieurs à 119119.
bannière à retenir

À retenir

En particulier, les nombres premiers inférieurs à 100100 sont :

22 33 55 77 1111
1313 1717 1919 2323 2929
3131 3737 4141 4343 4747
5353 5959 6161 6767 7171
7373 7979 8383 8989 9797

Nous avons déterminé l’ensemble des nombres premiers strictement inférieurs à 119119 et il ne semble pas y avoir de « schéma » ou de relation évidente entre eux.
Quels sont les autres nombres premiers ? Pouvons-nous tous les déterminer ou déterminer leur place dans N\mathbb N ? Nous allons nous intéresser à leur ensemble.

Ensemble des nombres premiers

bannière propriete

Propriété

Il y a une infinité de nombres premiers.

Nous allons démontrer cette propriété ; l’idée de cette démonstration vient d’un autre mathématicien de l’Antiquité, Euclide, dont nous connaissons déjà des travaux en arithmétique, comme l’utilisation des divisions euclidiennes et l’algorithme de recherche d’un PGCD\text{PGCD}.

bannière demonstration

Démonstration

  • On suppose par l’absurde qu’il y a un nombre fini ll de nombres premiers dans N\mathbb N.

Leur ensemble, classé par ordre coissant, est {p1,p2,,pl1,pl}\lbrace p1,\,p2,\,…,\,p{l-1},\,pl \rbrace.

  • Ils sont tous strictement supérieurs à 11.
  • Soit nn le nombre entier : n=p1×p2××pl+1n=p1 \times p2\times … \times p_l+1.

nn est strictement supérieur à tous les pipi de l’ensemble {p1,p2,,pl1,pl}\lbrace p1,\,p2,\,…,\,p{l-1},\,p_l \rbrace des nombres premiers.

  • D’après notre hypothèse, puisque plp_l est le plus grand nombre premier, nn n’est pas premier.
  • D’après la propriété que nous avons vue au point précédent, il existe donc un nombre premier inférieur à n\sqrt{n} qui le divise.

On note pkpk ce nombre premier : pk{p1,p2,,pl1,pl}pk\in \lbrace p1,\,p2,\,…,\,p{l-1},\,pl \rbrace

pkpk divise nn et pkpk divise p1×p2××plp1 \times p2\times …\times p_l.

  • Donc pkpk divise (np1×p2××pl)(n-p1\times p2\times … \times pl).
  • Or, n=p1×p2××pl+1n=p1 \times p2\times … \times p_l+1, donc :

np1×p2××pl=1n-p1 \times p2\times … \times p_l=1

  • Cela signifie que pkpk divise 11, et donc que pk=1pk=1 n’est pas premier, ce qui est contradictoire.
  • En conclusion, l’hypothèse de départ : « Il y a un nombre fini de nombres premiers », est fausse, et nous avons démontré la propriété.

Nous ne connaissons donc pas tous les nombres premiers ni comment les obtenir. Des études sont menées sur ces derniers, car leur connaissance permet d’obtenir des méthodes de codage et de chiffrement des données.
Pour le comprendre, nous devons d’abord nous intéresser au lien entre les nombres premiers et les autres nombres entiers.

Décomposition d’un nombre entier en facteurs premiers

En seconde, nous avons déjà vu qu’un nombre entier non premier pouvait s’écrire comme un produit de nombres premiers.
Par exemple, si nous considérons le nombre 280280, il peut s’écrire ainsi :

280=10×28=(2×5)×(7×4)=2×5×7×2×2\begin{aligned} 280&=10\times28 \ &=(2\times5)\times(7\times4) \ &=2\times5\times7\times2\times2 \ \end{aligned}

C’est un produit des nombres premiers 22, 55 et 77.

  • Nous pouvons l’écrire : 280=23×5×7280=2^3\times5\times7.

Cette décomposition est possible pour chacun des nombres entiers non premiers. C’est ce que nous allons voir avec les propriétés ci-dessous.

Existence et unicité de la décomposition

bannière propriete

Propriété

Soit n>2n>2, un nombre entier non premier.
nn est le produit de nombres premiers.

  • Autrement dit :

Il existe des nombres premiers p1p1, p2p2, …, pkpk distincts et des entiers a1a1, a2a2, …, akak appartenant à N\mathbb N^* tels que :

n=p1a1×p2a2××pk1ak1×pkakn= p1^{a1}\times p2^{a2}\times … \times p{k-1}^{a{k-1}}\times pk^{ak}

Cette décomposition de nn en produit de facteurs premiers est unique.

Dans l’exemple ci-dessus, 280=23×5×7280=2^3\times5\times7, les nombres premiers sont p1=2p1=2, p2=5p2=5 et p3=7p3=7, et les nombres a1a1, a2a2, a3a3 valent respectivement 33, 11 et 11.

bannière definition

Définition

Décomposition en produit de facteurs premiers :

Soit nn un nombre entier naturel non premier.

L’eˊcriture :n=p1a1×p2a2××pk1ak1×pkakavec, pour tout i{1,,k} : {pi est un nombre premieraiNs’appelle la deˊcomposition de n en produit de facteurs premiers.\begin{aligned} &\text{L’écriture\ :} \ &n= p1^{a1}\times p2^{a2}\times … \times p{k-1}^{a{k-1}}\times pk^{ak} \ &\text{avec, pour tout $i\in\lbrace 1,\,…,\,k \rbrace$\ :\ } \begin{cases} pi \text{ est un nombre premier} \ ai\in \mathbb N^* \end{cases} \ &\text{s’appelle la décomposition de nn en produit de facteurs premiers.} \end{aligned}

  • On dit aussi qu’on a décomposé nn en produit de facteurs premiers.

Nous allons démontrer l’existence de la décomposition en facteurs premiers. Le premier à avoir démontré cette propriété est Euclide.

bannière demonstration

Démonstration

Soit n>2n >2, un nombre entier non premier.

  • Nous savons que son plus petit diviseur est un nombre premier p1p_1 tel que :

2p1n<n2\leq p_1 \leq\sqrt{n}

  • Ainsi, nous pouvons écrire :

n=p1×q1 ouˋ {q1N2p1<q1<nn=p1\times q1 \footnotesize{\textcolor{#A9A9A9}{\text{ où } \begin{cases} q1\in \mathbb N \ 2\leq p1 < q_1< n \end{cases}}}

  • Si q1q1 est premier, nous avons démontré la propriété : n=p1×q1n=p1\times q1, où p1p1 et q1q_1 sont des nombres premiers.
  • Si q1q_1n’est pas premier, alors nous pouvons lui appliquer le même raisonnement que nous avons mené pour nn.

q1q1 n’est pas premier, donc il admet un plus petit diviseur premier p2p2 et on peut écrire :

q1=p2×q2 ouˋ {q2N2q2<q1<net : n=p1×p2×q2\begin{aligned} q1 &= p2\times q2 \footnotesize{\textcolor{#A9A9A9}{\text{ où } \begin{cases} q2\in \mathbb N \ 2\leq q2 < q1< n \end{cases}}} \ \textcolor{#A9A9A9}{\text{et\ : }}n&= p1\times p2\times q_2 \end{aligned}

  • Nous pouvons mener de nouveau ce raisonnement avec le nombre q2q_2.
  • Et ainsi de suite.
  • Nous allons donc obtenir une suite décroissante d’entiers naturels qiq_i, tous supérieurs ou égaux à 22.
  • Cette suite sera donc composée d’un nombre fini de nombres entiers.

Cela signifie que la décomposition s’arrête et nous arrivons à :

2ql1<<q1 et : n=p1×p2××pl1×ql1\begin{aligned} &2\leq q_{l-1} < …

Au dernier ql1q_{l-1}, on ne peut trouver un diviseur premier strictement inférieur, car sinon il ne serait pas le dernier.

  • Donc ql1q{l-1} est premier. On peut le noter plpl.

Cela donne donc la décomposition :

n=p1×p2××pl1×plouˋ les pi sont des nombres premiers\begin{aligned} &n=p1\times p2\times … \times p{l-1}\times pl \ &\footnotesize{\textcolor{#A9A9A9}{\text{où les $p_i$ sont des nombres premiers}}} \end{aligned}

  • En regroupant les valeurs égales de certains nombres premiers, nous obtenons la forme :

n=p1a1×p2a2××pk1ak1×pkakn= p1^{a1}\times p2^{a2}\times … \times p{k-1}^{a{k-1}}\times pk^{ak}

  • Nous admettrons que cette décomposition est unique.

Remarque :
Si nnest un nombre premier, il ne peut pas être décomposé de la sorte.

bannière à retenir

À retenir

Ainsi, si n>2n>2 :

  • soit il est premier ;
  • soit il peut être décomposé en produit de facteurs premiers.
bannière astuce

Astuce

Ces deux propriétés – existence et unicité – de la décomposition en produit de facteurs premiers sont connues comme le théorème fondamental de l’arithmétique.
Il stipule en effet que les nombres premiers « génèrent » par produit l’ensemble des nombres entiers naturels.

Pour trouver la décomposition en facteurs premiers de nn,nous allons rappeler la méthode vue en seconde, et qui sera utilisée quand nn est relativement grand.

bannière à retenir

À retenir

Méthodologie :

  • On teste la divisibilité de nn par les nombres premiers dans l’ordre croissant.

Pour cela, nous pouvons nous aider des critères de divisibilité et de la liste des diviseurs premiers inférieurs à 100100.

  • Soit pp le plus petit nombre premier qui divise nn.
  • On trouve le quotient qq de nn par pp : n=qpn=qp.
  • On teste de nouveau la divisibilité de qq par pp :
  • si qq est divisible par pp, on procède comme ci-dessus, on trouve son quotient et on teste sa divisibilité par pp ;
  • sinon, on teste la divisibilité de qq par le nombre premier immédiatement supérieur à pp.
  • On continue ce procédé jusqu’à obtenir un quotient égal à 11.

Prenons un exemple pour illustrer cette méthode, qui est un algorithme que nous pourrions programmer.

bannière exemple

Exemple

Nous voulons décomposer 53555\,355 en produit de facteurs premiers.

  • L’utilisation des critères de divisibilité que nous connaissons prouve que 53555\,355 n’est pas divisible par 22, mais qu’il est divisible par 33 (puisque 5+3+5+5=185+3+5+5=18 est un multiple de 3)3).
  • Nous avons : 5355=3×17855\, 355 =3\times1\,785.
  • Le quotient de cette division euclidienne est 17851\,785. Testons de nouveau la divisibilité de 17851\,785 par 33.
  • 1785=3×5951\,785=3\times595
  • Ensuite, 595595 n’est pas divisible par 33, mais il est divisible par le nombre premier suivant…
  • On continue ainsi par des divisions successives jusqu’à obtenir le quotient 11.

Pour schématiser ces divisions successives, nous pouvons les noter dans un tableau.

Quotient Division par
53555\,355 33
17851\,785 33
595595 55
119119 77
1717 1717
11
  • Nous lisons donc dans la colonne de droite la décomposition de 53555\,355 en produit de facteurs premiers :

5355=32×5×7×175\,355= 3^2\times5\times7\times17

  • Cette décomposition est unique selon la propriété ci-dessus.

Nous allons maintenant nous intéresser à l’ensemble des diviseurs d’un nombre entier, à partir de cette décomposition.

Diviseurs d’un nombre entier naturel

Reprenons l’exemple de la décomposition de 53555\,355.

  • Nous cherchons comment obtenir tous les diviseurs de 53555\,355 et leur nombre.

Si dd est un diviseur de 53555\,355, alors dd divise 32×5×7×173^2\times5\times7\times17.

  • Si dd est premier, alors dd est nécessairement 33, 55, 77 ou 1717.
  • Sinon, soit pap^a un facteur de la décomposition en facteurs premiers de dd.

pap^a divise dd et dd divise 32×5×7×173^2\times5\times7\times17.

  • Donc, par transitivité, pap^a divise 32×5×7×173^2\times5\times7\times17.

Comme la décomposition de 53555\,355 en produit de facteurs premiers est unique, cela signifie que pap^a doit nécessairement être un facteur de la décomposition de 53555\,355.

  • On en déduit que la forme des diviseurs de 53555\,355 est :

3a1×5a2×7a3×17a4avec : {0a120a210a310a41\begin{aligned} &3^{a1}\times5^{a2}\times7^{a3}\times17^{a4 } \ &\footnotesize{\textcolor{#A9A9A9}{\text{avec\ : } \begin{cases} 0\leq a1 \leq 2 \ 0\leq a2 \leq 1 \ 0\leq a3 \leq 1 \ 0\leq a4 \leq 1 \end{cases}}} \end{aligned}

Il y a 33 valeurs possibles pour a1a1, 22 valeurs possibles pour a2a2, ainsi que pour a3a3 et a4a4.

  • Il y a donc 3×2×2×2=243\times2\times2\times2=24 diviseurs de 53555\,355.

En nous appuyant sur cet exemple, nous en déduisons la forme des diviseurs d’un nombre nn non premier.

bannière propriete

Propriété

Soit nn un nombre entier naturel non premier dont la décomposition en facteurs premiers est :

n=p1a1×p2a2××pk1ak1×pkakn= p1^{a1}\times p2^{a2}\times … \times p{k-1}^{a{k-1}}\times pk^{ak}

Les diviseurs positifs de nn sont les nombres entiers naturels de la forme :

p1b1×p2b2××pk1bk1×pkbkouˋ biN et 0biai pour tout entier naturel i entre 1 et k\begin{aligned} &p1^{b1}\times p2^{b2}\times … \times p{k-1}^{b{k-1}}\times pk^{bk} \ &\footnotesize{\textcolor{#A9A9A9}{\text{où $b_i\in \mathbb N^*$ et $0\leq b_i\leq a_i$ pour tout entier naturel $i$ entre 11 et $k$}}} \end{aligned}

Prenons un exemple pour illustrer cette propriété.

bannière exemple

Exemple

Nous avons vu que 280=23×5×7280=2^3\times5\times7.
Les diviseurs de 280280 sont donc les nombres entiers :

2a1×5a2×7a3ouˋ {a1 peut valoir 012 ou 3a2 et a3 peuvent valoir 0 ou 1\begin{aligned}&2^{a1}\times5^{a2}\times7^{a3} \ &\footnotesize{\textcolor{#A9A9A9}{\text{où } \begin{cases}a1 \text{ peut valoir 00, 11, 22 ou 33} \ a_2 \text{ et $a_3$ peuvent valoir 00 ou 11} \end{cases}}} \end{aligned}

  • 4×5=204\times5=20 est donc un diviseur de 280280 ; 2×5×7=702\times5\times7=70 également.
  • 2×522\times5^2 n’est pas un diviseur de 280280 ; non plus que 2×5×112\times5\times11.

Cette propriété va nous permettre également de résoudre certaines équations comme dans l’exemple ci-dessous.

bannière exemple

Exemple

Nous voulons résoudre dans N\mathbb N, l’équation (E):x(x2+5x24)=130(E): x(x^2+5x-24)=130.

  • Pour résoudre cette équation de degré 33 dans N\mathbb N, nous allons factoriser l’expression polynomiale et nous servir de la décomposition en facteurs premiers de 130130.
  • D’une part, nous factorisons en utilisant la forme canonique ou le calcul du discriminant :

x2+5x24=(x3)(x+8)x^2+5x-24=(x-3)(x+8)

  • D’autre part, on décompose 130130 en produit de facteurs premiers :

130=10×13=2×5×13\begin{aligned} 130 &=10\times13\ &=2\times5\times13 \end{aligned}

  • Nous avons ainsi :

(E)x(x3)(x+8)=2×5×13\begin{aligned} (E)\Leftrightarrow x(x-3)(x+8)=2\times5\times13 \end{aligned}

Les nombres entiers xx, x3x-3 et x+8x+8 sont des diviseurs de 130130 et cela implique que les trois nombres sont strictement positifs.

  • xx, x3x-3 et x+8x+8 appartiennent donc à l’ensemble :

{1,2,5,2×5,13,2×13,5×13,130}={1,2,5,10,13,26,65,130}\lbrace 1,\,2,\,5,\,2\times5,\,13,\,2\times13,\,5\times13,\,130\rbrace=\lbrace 1,\,2,\,5,\,10,\,13,\,26,\,65,\,130\rbrace

Nous cherchons dans cette liste un entier xx tel que x3x-3 et x+8x+8 y soient aussi. La seule solution est x=5x=5.

  • Ainsi, dans N\mathbb N, (E)x=5(E)\Leftrightarrow x=5.

Enfin, une des applications du théorème fondamental de l’arithmétique est de trouver le PGCD\text{PGCD} de deux nombres entiers naturels.

Application : PGCD\text{PGCD} de deux nombres de N\mathbb N^*

Nous retrouvons la propriété sur le PGCD\text{PGCD} de deux nombres que nous avons vue dans le cours précédent.

bannière propriete

Propriété

Soit aa et bb deux nombres de N{0,1}\mathbb N \smallsetminus \lbrace0,\,1\rbrace non premiers entre eux.
PGCD(a ;b)\text{PGCD} (a\ ;\, b) est le produit des nombres premiers communs à leur décomposition en facteurs premiers, affectés du plus petit exposant.

bannière exemple

Exemple

Nous cherchons PGCD(1960 ;5355)\text{PGCD}(1960\ ;\, 5\,355).
Nous avons établi que :

5355=32×5×7×17et : 1960=280×7=23×5×72\begin{aligned} 5\,355&= 3^2\times5\times7\times17 \ \textcolor{#A9A9A9}{\text{et\ :\ }} 1\,960&=280\times7 \ &=2^3\times5\times7^2 \ \end{aligned}

Les facteurs premiers communs aux deux décompositions sont 55 et 77.

  • Dans la première décomposition, l’exposant de 55 est 11, comme dans la deuxième.
  • Dans la première décomposition, l’exposant de 77 est 11 ; il est égal à 22 dans la deuxième.
  • Nous en déduisons :

PGCD(1960 ;5355)=5×7=35\begin{aligned} \text{PGCD} (1\,960\ ;\, 5\,355) &= 5 \times 7 \ &=35 \end{aligned}

Nous nous sommes intéressés à la décomposition des nombres entiers en facteurs de nombres premiers. Ces algorithmes deviennent ardus quand le nombre entier est très grand, même avec les ordinateurs d’aujourd’hui.
Nous allons maintenant examiner un théorème important de l’arithmétique qui permet notamment de déterminer la divisibilité de très grands nombres par des nombres premiers.

Petit théorème de Fermat

Pierre de Fermat est un mathématicien français qui vécut au XVIIesiècle et travailla surtout sur les nombres. Il écrivit de nombreuses propriétés arithmétiques, mais ne fournit pas toujours de démonstrations écrites.
Certaines conjectures sont en en cours d’analyse de nos jours, certaines ont été prouvées ou contredites plusieurs siècles plus tard. Le petit théorème de Fermat a notamment été démontré par le mathématicien Léonard Euler, qui vécut au XVIIIe siècle.

Petit théorème de Fermat

Nous admettons le résultat suivant.

bannière theoreme

Théorème

Soit nNn\in \mathbb N^* et pp est un nombre premier qui ne divise pas nn.
Alors pp divise np11n^{p-1}-1, c’est-à-dire :

np11[p]n^{p-1}\equiv 1\,\lbrack p \rbrack

Prenons un exemple d’application directe de ce théorème.

bannière exemple

Exemple

Nous cherchons le reste dans la division euclidienne de 12612^6 par 77.
77 est un nombre premier qui ne divise pas 1212.
Nous pouvons donc appliquer le petit théorème de Fermat et déduire que :

12711[7] donc : 1261[7]12^{7-1}\equiv\, 1\lbrack 7 \rbrack \textcolor{#A9A9A9}{\text{ donc\ : }} 12^6\equiv 1\,\lbrack 7 \rbrack

  • Ainsi, le reste dans la division euclidienne de 12612^6 par 77 est 11.

Ce théorème permet de résoudre des équations à congruence avec de grands nombres. Pour nous en convaincre, prenons un autre exemple.

bannière exemple

Exemple

Nous voulons résoudre l’équation (E):x623[11](E)\,:\, x^{62}\equiv 3\,\lbrack 11 \rbrack dans N\mathbb N.

  • 1111 est un nombre premier. Nous n’avons pas x111x^{11-1}, soit x10x^{10}, dans cette équation, ce qui pourrait faire penser directement au petit théorème de Fermat ; nous allons donc le faire apparaître !

Nous effectuons la division euclidienne de 6262 par 1010 : 62=10×6+262=10\times6+2.

  • Ainsi : (E)(x6)10x23[11](E) \Leftrightarrow \left(x^6 \right)^{10} x^2\equiv 3\, \lbrack 11 \rbrack.
  • Repérons deux cas.
  • Si 1111 divise xx, alors 1111 divise x62x^{62}.
  • Les multiples de 1111 ne sont pas solutions de (E)(E), car alors :

x620[11]x^{62}\equiv 0\, \lbrack 11 \rbrack

  • Si 1111 ne divise pas xx, comme 1111 est premier avec xx, il ne divise pas x6x^6 non plus.

Ainsi, nous pouvons appliquer le petit théorème de Fermat à x6x^6, avec p=11p=11.
Nous avons donc :

(x6)101[11]{(x^6)}^{10}\equiv 1\, \lbrack 11 \rbrack

  • La congruence est compatible avec la multiplication, donc, si 1111 ne divise pas xx, nous avons :

(E)x23[11](E)\Leftrightarrow x^2\equiv 3\, \lbrack 11 \rbrack

  • Intéressons-nous maintenant au reste de la division euclidienne de x2x^2 par 1111.

Nous utilisons, comme dans le cours sur la divisibilité dans Z\mathbb Z, la propriété suivante.

bannière rappel

Rappel

Si ab[n]a\equiv b\lbrack n \rbrack, alors apbp[n]a^p\equiv b^p \lbrack n \rbrack.

Nous allons maintenant procéder comme nous l’avons appris dans le cours sur la congruence.

  • Si x0[11]x\equiv 0\,\,\lbrack 11 \rbrack, nous avons :

x20[11]x^2\equiv 0\,\,\lbrack 11 \rbrack

  • Si x1[11]x\equiv 1\,\lbrack 11 \rbrack, nous avons :

x21[11]x^2\equiv 1\,\lbrack 11 \rbrack

  • Si x2[11]x\equiv 2\,\lbrack 11 \rbrack, nous avons :

x24[11]x^2\equiv 4\,\lbrack 11 \rbrack

  • Si x3[11]x\equiv 3\,\lbrack 11 \rbrack, nous avons :

x29[11]x^2\equiv 9\,\lbrack 11 \rbrack

  • Si x4[11]x\equiv 4\,\lbrack 11 \rbrack, nous avons :

x216[11]5[11]\begin{aligned} x^2&\equiv 16\,\lbrack 11 \rbrack \ &\equiv 5\,\lbrack 11 \rbrack \end{aligned}

  • Si x5[11]x\equiv 5\,\lbrack 11 \rbrack, nous avons :

x225[11]3[11]\begin{aligned} x^2&\equiv 25\,\lbrack 11 \rbrack \ &\equiv 3\,\lbrack 11 \rbrack \end{aligned}

  • Si x6[11]x\equiv 6\,\lbrack 11 \rbrack, nous avons :

x236[11]3[11]\begin{aligned} x^2&\equiv 36\,\lbrack 11 \rbrack \ &\equiv 3\,\lbrack 11 \rbrack \end{aligned}

  • Si x7[11]x\equiv 7\,\lbrack 11 \rbrack, nous avons :

x249[11]5[11]\begin{aligned} x^2&\equiv 49\,\lbrack 11 \rbrack \ &\equiv 5\,\lbrack 11 \rbrack \end{aligned}

  • Si x8[11]x\equiv 8\,\lbrack 11 \rbrack, nous avons :

x264[11]9[11]\begin{aligned} x^2&\equiv 64\,\lbrack 11 \rbrack \ &\equiv 9\,\lbrack 11 \rbrack \end{aligned}

  • Si x9[11]x\equiv 9\,\lbrack 11 \rbrack, nous avons :

x281[11]4[11]\begin{aligned} x^2&\equiv 81\,\lbrack 11 \rbrack \ &\equiv 4\,\lbrack 11 \rbrack \end{aligned}

  • Si x10[11]x\equiv 10\,\lbrack 11 \rbrack, nous avons :

x2100[11]1[11]\begin{aligned} x^2&\equiv 100\,\lbrack 11 \rbrack \ &\equiv 1\,\lbrack 11 \rbrack \end{aligned}

  • Nous obtenons le tableau :

x modulo 11x \text{ modulo } 11 $0$ $1$ $2$ $3$ 44 55 66 77 88 99 1010
x2 modulo 11x^2 \text{ modulo } 11 $0$ $1$ 44 99 55 3\red3 3\red3 55 99 44 $1$
  • En conclusion :

x23[11]x5[11] ou x6[11]x^2\equiv\, 3 \lbrack 11 \rbrack\Leftrightarrow x\equiv 5\, \lbrack 11 \rbrack \text{ ou } x\equiv 6\,\lbrack 11 \rbrack

  • Les solutions de l’équation (E)(E) dans N\mathbb N sont donc :

{11k+5,11k+6 ;kN}\lbrace 11k+5,\, 11k+6\ ;\, k\in \mathbb N\rbrace

Ces exemples illustrent le cas où le nombre premier pp ne divise pas nn.
Nous disposons également d’un corollaire qui s’applique à n’importe quel entier naturel nn.

Corollaire du petit théorème de Fermat

bannière propriete

Propriété

Soit pp un nombre premier et nNn\in \mathbb N.
Alors pp divise npnn^p-n, c’est-à-dire :

npn[p]n^p\equiv n\,\lbrack p \rbrack

bannière demonstration

Démonstration

Soit nNn\in \mathbb N et pp un nombre premier :

npn=n(np11)n^p-n=n(n^{p-1}-1)

  • Si pp divise nn, alors pp divise n(np11)n(n^{p-1}-1).
  • Sinon, le petit théorème de Fermat nous assure que np11[p]n^{p-1}\equiv 1\,[p].
  • Donc pp divise np11n^{p-1}-1.
  • Dans les deux cas, pp divise n(np11)n(n^{p-1}-1), ce qui donne la relation : pp divise npnn^p-n.
  • Nous avons donc :

npn[p]n^p\equiv n\,[p]

bannière astuce

Astuce

L’intérêt de ce corollaire peut être énoncé ainsi : un entier nn élevé à la puissance du nombre premier pp a le même reste dans la division euclidienne par pp que $n$.

Prenons un exemple d’application de cette propriété.

bannière exemple

Exemple

Nous cherchons à montrer que 1313 divise 1113+151311^{13}+15^{13}.

1313 est un nombre premier, donc on peut appliquer le corollaire ci-dessus :

111311[13]151315[13]\begin{aligned} 11^{13}&\equiv 11\,\lbrack 13 \rbrack \ 15^{13}&\equiv 15\,\lbrack 13 \rbrack \end{aligned}

La congruence est compatible avec l’addition, donc :

1113+151311+15[13]26[13]0[13]\begin{aligned} 11^{13}+15^{13}&\equiv 11+15 \,\lbrack 13 \rbrack \ &\equiv 26\,\lbrack 13 \rbrack \ &\equiv 0\,\lbrack 13 \rbrack \end{aligned}

  • Nous en déduisons que 1313 divise 1113+151311^{13}+15^{13}.

Cet exemple prouve l’efficacité du petit théorème de Fermat et de son corollaire quand il s’agit de déterminer la divisibilité ou la congruence de très grands nombres par des nombres premiers.

Conclusion :

Dans ce cours, nous avons abordé quelques notions du vaste champ d’étude des nombres premiers : leur définition, quelques algorithmes pour les reconnaître et quelques propriétés fondamentales.

Des applications nombreuses et actuelles utilisent les grands nombres premiers, qui ne sont pas encore très connus, pour chiffrer ou déchiffrer des données, notamment dans le commerce électronique ou la cryptographie ; c’est pourquoi l’arithmétique reste une branche active de la recherche en mathématiques.