Théorie > Théorie des nombres > Divisibilité et nombres premiers

Prérequis

Aucun prérequis.

Résumé

La division est l'ingrédient principal de la théorie des nombres, et c'est sur cette notion que nous nous penchons ici. À l'aide de quelques formules connues, nous montrons qu'il est déjà possible sans nouvelle théorie de résoudre des problèmes non évidents de théorie des nombres. Il est en effet souvent possible de conclure avec un peu de logique et quelques distinctions de cas. La résolution de problèmes plus avancés commencera aussi avant tout par de telles méthodes.

Ce chapitre a été écrit par N. Radu et mis en ligne le 8 décembre 2014.

1. Divisibilité

La notion primordiale en théorie des nombres est celle de divisibilité. La définition suivante, bien que basique, n'en est donc pas moins importante :

Définition
Si $a$ et $b$ sont deux entiers positifs, on dit que $a$ est multiple de $b$, $a$ est divisible par $b$, ou encore que $b$ divise $a$ s'il existe un nombre entier $k$ tel que $a = k \cdot b$. On note alors $b \mid a$.

Remarque : Il est bon de constater que $0$ est multiple de tous les entiers alors que $1$ les divise tous.

Il est bien évidemment possible d'étendre cette définition aux nombres négatifs ($-5$ diviserait $10$ puisque $10 = (-5)\cdot(-2)$). Cela n'ajoute aucune difficulté et il peut arriver de manipuler ainsi des nombres négatifs, mais nous n'allons considérer que des nombres positifs dans la suite de ce chapitre afin d'éviter toute ambiguïté.

2. Nombres premiers

Définitions

Commençons avec la définition d'un nombre premier, qu'il est toujours bon de rappeler.

Définition
Un nombre premier est un nombre naturel qui possède exactement deux diviseurs (positifs).

Vu qu'un nombre $n \in \mathbb{N}$ est toujours divisible par $1$ et par $n$, cela signifie intuitivement qu'il ne doit posséder aucun diviseur différent de $1$ et lui-même. Par exemple, $5$ est un nombre premier car il n'est divisible que par $1$ et $5$.

Attention : Une faute très courante due à cette "intuition" est de penser que $1$ est un nombre premier. Il n'en est rien ! Certes, il ne possède aucun diviseur différent de $1$ et lui-même, mais il ne possède pas exactement deux diviseurs : il n'en a qu'un seul ! Les premiers nombres premiers sont donc $2, 3, 5, 7, 11, 13, 17, \dots$

Définition
On dit qu'un nombre naturel non-nul est composé s'il est différent de $1$ et non-premier.

Un premier résultat concernant les nombres premiers est le suivant.

Proposition
Il existe une infinité de nombres premiers.

Démonstration
On procède par l'absurde, en supposant qu'il existe seulement un nombre fini de nombres premiers. On note alors ceux-ci $p_1, p_2, \ldots, p_k$. On considère alors le nombre $q = p_1\cdot p_2 \cdot \ldots \cdot p_k + 1$. Ce nombre n'étant visiblement divisible par aucun des $p_i$, il doit être premier lui aussi. C'est absurde, puisqu'il est différent des $p_i$ et qu'on a supposé qu'il s'agissait des seuls nombres premiers.

Décomposition en facteurs premiers

Aussi appelé théorème fondamental de l'arithmétique, le théorème de décomposition en produit de facteurs premiers nous dit la chose suivante.

Théorème fondamental de l'arithmétique
Tout entier strictement positif peut être écrit comme un produit de nombres premiers, et ce d'une unique façon à l'ordre près des facteurs.

Autrement dit, pour tout $n \in \mathbb{N}_0$ il existe d'uniques nombres premiers $p_1 < p_2 < \ldots < p_k$ et des entiers strictement positifs $e_1, e_2, \dots, e_k$ tels que
$$ n = p_1^{e_1} \cdot p_2^{e_2} \cdot \ldots \cdot p_k^{e_k}.$$

Par exemple, la décomposition en facteurs premiers de $90$ est
$$90 = 2 \cdot 3^2 \cdot 5.$$ Comme dans cet exemple, on sous-entend généralement les exposants égaux à $1$.

Le théorème est un peu ambigu pour $n = 1$. On considère en fait que $1$ est égal au produit de zéro nombre premier. Bien que peu intuitif, cela peut s'expliquer par le fait que multiplier par $1$ revient à ne multiplier par rien du tout.

3. Diviseurs

Une question naturelle, étant donné un nombre $n \in \mathbb{N}_0$, est de se demander combien il possède de diviseurs. Si la décomposition en facteurs premiers du nombre $n$ est connue, alors il existe une formule très simple :

Formule (nombre de diviseurs)
Si $n \in \mathbb{N}_0$ possède la décomposition
$$ n = p_1^{e_1} \cdot p_2^{e_2} \cdot \ldots \cdot p_k^{e_k}$$ alors $n$ possède exactement $(e_1+1)\cdot(e_2+1)\cdot \ldots \cdot (e_k+1)$ diviseurs (positifs).

Pour reprendre l'exemple précédent, $90 = 2^1 \cdot 3^2 \cdot 5^1$ possède exactement $(1+1)\cdot(2+1)\cdot(1+1) = 12$ diviseurs positifs. On peut le vérifier à la main puisque les diviseurs de $90$ sont $1$, $2$, $3$, $5$, $6$, $9$, $10$, $15$, $18$, $30$, $45$, et $90$.

Démonstration
Étant donnée la décomposition de $n$, il semble évident qu'un nombre $m$ ne pourra diviser $n$ que si sa décomposition est de la forme
$$ m = p_1^{f_1} \cdot p_2^{f_2} \cdot \ldots \cdot p_k^{f_k}$$ où chaque $f_i$ est compris entre $0$ et $e_i$ inclus (un exposant $0$ revenant à ne pas écrire $p_i$ puisque $p_i^0 = 1$ par convention).
Dès lors, le nombre de diviseurs $m$ de $n$ est exactement égal au nombre de façons de choisir les valeurs des $f_i$. Puisqu'il y a $e_i + 1$ possibilités pour $f_i$, il y a au total $(e_1+1)\cdot(e_2+1)\cdot \ldots \cdot (e_k+1)$ telles façons de faire.

4. Formules

Les formules remarquables suivantes peuvent paraître anodines mais se révèlent en fait être très utilisées dans la résolution de problèmes. Il est donc bon de les connaître.

Cas simple

Lorsque nous sommes en présence d'une somme ou d'une différence de deux cubes, il est toujours possible de décomposer ce terme en produit de deux facteurs comme suit :
$$a^3 - b^3 = (a-b)(a^2 +ab + b^2),$$ $$a^3 + b^3 = (a+b)(a^2 - ab + b^2).$$ Il suffit de développer les membres de droite pour constater que ces formules sont bel et bien vraies.

Cas général

Il est possible de généraliser ces formules pour des puissances $n$-èmes. Pour la première, nous avons en fait :
$$a^n - b^n = (a-b)(a^{n-1} + a^{n-2}b + a^{n-3}b^2 + \ldots + ab^{n-2} + b^{n-1}) \quad \text{pour tout } n\in \mathbb{N}_0.$$ Pour ce qui est de la somme de deux puissances, nous avons également une généralisation mais il est important de garder en tête que celle-ci n'est valable que pour les puissances impaires (il n'est par exemple pas possible de décomposer $a^2 + b^2$ en produit de deux facteurs) :
$$a^n + b^n = (a+b)(a^{n-1} - a^{n-2}b + a^{n-3}b^2 - \ldots - ab^{n-2} + b^{n- 1}) \quad \text{pour tout } n \in \mathbb{N}_0 \text{ impair}.$$ À noter que cette fois, le deuxième facteur de la décomposition contient des termes alternés (un terme sur deux est précédé d'un signe $+$).
Ces deux formules peuvent également être prouvées en développant les membres de droite. En fait, la deuxième peut être obtenue de la première en remplaçant $b$ par $-b$ (ce qui explique pourquoi $n$ doit être impair).

Remarques

  1. Vu que la théorie des nombres s'intéresse généralement à la divisibilité des nombres, ce que l'on utilise souvent est le fait que $a-b$ divise $a^n- b^n$ pour tout $n$ et que $a+b$ divise $a^n + b^n$ pour tout $n$ impair. Il n'est cependant pas rare de devoir connaître la forme du deuxième facteur et nous conseillons donc vivement de connaître ces deux formules.

  2. Un cas particulier de ces formules, souvent pratique, est celui où $b = 1$. Dans ce cas, on a
    $$x^n - 1 = (x- 1)(x^{n-1} + x^{n-2} + \ldots + x + 1)$$ pour tout $n \in \mathbb{N}_0$ et
    $$x^n + 1 = (x+1)(x^{n-1}-x^{n-2}+\ldots-x+1)$$ seulement lorsque $n$ est impair.