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 :

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