Nombres premiers et petit théorème de Fermat

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$.
Ce contenu est réservé à nos inscrits. Il reste 50% à lire.
Inscrivez-vous gratuitement pour lire la suite
Inscrivez-vous pour lire la suite et accéder à nos vidéos, quiz, exercices, méthodes… Tout ce qu’il faut pour augmenter sa moyenne. 😉