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 !

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.