Nombres premiers et petit théorème de Fermat

information-icon

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

Nombres premiers

  • Soit $n\in\mathbb N$.
  • $n$ est un nombre premier lorsqu’il a exactement deux diviseurs entiers naturels distincts : $1$ et lui-même.
  • Pour montrer qu’un nombre $n$ n’est pas premier, il suffit de trouver un diviseur de $n$ différent de $1$ et de lui-même. On essaiera donc d’écrire $n$ comme un produit de nombres entiers.
  • Il y a une infinité de nombres premiers.
  • Soit $n \in \mathbb N$, avec $n\geq4$.
  • Si $n$ n’est pas un nombre premier, alors $n$ admet au moins un diviseur premier $p$ tel que $2\leq p\leq \sqrt{n}$.
  • Si $n$ n’admet aucun diviseur premier inférieur à $\sqrt n$, alors $n$ est un nombre premier.
  • En particulier, les nombres premiers inférieurs à $100$ sont :

$2$ $3$ $5$ $7$ $11$
$13$ $17$ $19$ $23$ $29$
$31$ $37$ $41$ $43$ $47$
$53$ $59$ $61$ $67$ $71$
$73$ $79$ $83$ $89$ $97$
  • Soit $n>2$, un nombre entier non premier.
  • $n$ est le produit de nombres premiers : il existe des nombres premiers $p_1$, $p_2$, …, $p_k$ distincts et des entiers $a_1$, $a_2$, …, $a_k$ appartenant à $\mathbb N^*$ tels que :

$$n= p_1^{a_1}\times p_2^{a_2}\times … \times p_{k-1}^{a_{k-1}}\times p_k^{a_k}$$

  • Cette décomposition de $n$ en produit de facteurs premiers est unique.
  • Soit $n$ un nombre entier naturel non premier.
  • L’écriture suivante s’appelle la décomposition de $n$ en produit de facteurs premiers :

$$\begin{aligned} &n= p_1^{a_1}\times p_2^{a_2}\times … \times p_{k-1}^{a_{k-1}}\times p_k^{a_k} \\ &\text{avec, pour tout $i\in\lbrace 1,\,…,\,k \rbrace$\ :\ } \begin{cases} p_i \text{ est un nombre premier} \\ a_i\in \mathbb N^* \end{cases} \end{aligned}$$

  • Si $n>2$, soit il est premier, soit il peut être décomposé en produit de facteurs premiers.
  • Méthodologie pour décomposer $n$ en produit de facteurs premiers :
  • On teste la divisibilité de $n$ par les nombres premiers dans l’ordre croissant.
  • Soit $p$ le plus petit nombre premier qui divise $n$.
  • On trouve le quotient $q$ de $n$ par $p$ : $n=qp$.
  • On teste de nouveau la divisibilité de $q$ par $p$ :
  • si $q$ est divisible par $p$, on procède comme ci-dessus, on trouve son quotient et on teste sa divisibilité par $p$ ;
  • sinon, on teste la divisibilité de $q$ par le nombre premier immédiatement supérieur à $p$.
  • On continue ce procédé jusqu’à obtenir un quotient égal à $1$.
  • Soit $n$ un nombre entier naturel non premier dont la décomposition en facteurs premiers est : $n= p_1^{a_1}\times p_2^{a_2}\times … \times p_{k-1}^{a_{k-1}}\times p_k^{a_k}$.
  • Les diviseurs positifs de $n$ sont les nombres entiers naturels de la forme :

$$\begin{aligned} &p_1^{b_1}\times p_2^{b_2}\times … \times p_{k-1}^{b_{k-1}}\times p_k^{b_k} \\ &\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 $a$ et $b$ deux nombres de $\mathbb N \smallsetminus \lbrace0,\,1\rbrace$ non premiers entre eux.
  • $\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 $n\in \mathbb N^*$ et $p$ est un nombre premier qui ne divise pas $n$.
  • $p$ divise $n^{p-1}-1$ :

$$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 $p$ un nombre premier et $n\in \mathbb N$.
  • $p$ divise $n^p-n$ :

$$n^p\equiv n\,\lbrack p \rbrack$$

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