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 !

Si tu es un lycéen en terminale, tu dois déjà avoir planifié tes révisions pour ton baccalauréat 2022. Si ce n’est pas le cas, tu peux te baser sur notre programme de révision en le planifiant en fonction des épreuves ou des coefficients des matières … 💪

Nombres premiers

  • Soit nNn\in\mathbb N.
  • nn est un nombre premier lorsqu’il a exactement deux diviseurs entiers naturels distincts : 11 et lui-même.
  • 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. On essaiera donc d’écrire nn comme un produit de nombres entiers.
  • Il y a une infinité de nombres premiers.
  • Soit 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}.
  • Si nn n’admet aucun diviseur premier inférieur à n\sqrt n, alors nn est un nombre premier.
  • 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
  • Soit n>2n>2, un nombre entier non premier.
  • nn est le produit de nombres premiers : 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.
  • Soit nn un nombre entier naturel non premier.
  • L’écriture suivante s’appelle la décomposition de nn en produit de facteurs premiers :

n=p1a1×p2a2××pk1ak1×pkakavec, pour tout i{1,,k} : {pi est un nombre premieraiN\begin{aligned} &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} \end{aligned}

  • Si n>2n>2, soit il est premier, soit il peut être décomposé en produit de facteurs premiers.
  • Méthodologie pour décomposer nn en produit de facteurs premiers :
  • On teste la divisibilité de nn par les nombres premiers dans l’ordre croissant.
  • 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.
  • 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 $1$ et $k$}}} \end{aligned}

  • 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.

Petit théorème de Fermat

  • Petit théorème de Fermat : Soit nNn\in \mathbb N^* et pp est un nombre premier qui ne divise pas nn.
  • pp divise np11n^{p-1}-1 :

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

  • Ce théorème permet de résoudre des équations à congruence avec de grands nombres.
  • Corollaire : Soit pp un nombre premier et nNn\in \mathbb N.
  • pp divise npnn^p-n :

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

  • 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 nn.