Trop d’entiers pour trop peu de nombres premiers

On peut prouver qu'il existe une infinité de nombres premiers sans chercher à en construire un nouveau. L'idée de ce problème est différente : supposons qu'il n'existe qu'un nombre fini de nombres premiers, puis comptons combien d'entiers on pourrait fabriquer avec eux. Le conflit viendra du dénombrement lui-même.

Résultat fourni. Tout entier $n\ge 2$ peut s'écrire comme un produit de nombres premiers. On ne demande ni de démontrer ce résultat ni d'en connaître l'unicité. Pour $n=1$, on utilisera la convention qu'un produit ne contenant aucun facteur vaut $1$.

I — Mettre de côté les carrés

On donne les décompositions

$$72=2^3\times 3^2, \qquad 540=2^2\times 3^3\times 5.$$

(a) Écrire chacun de ces deux entiers sous la forme $n=ab^2$, où $a$ est un produit de nombres premiers distincts.

(b) Dans chaque exemple, comparer les nombres premiers qui apparaissent dans $a$ avec la parité des exposants de la décomposition donnée.

2. Soit $n\ge 2$. Dans une écriture de $n$ comme produit de puissances de nombres premiers distincts, regrouper, pour chaque nombre premier, les facteurs par paires. Montrer qu'il existe alors deux entiers $a\ge 1$ et $b\ge 1$ tels que

$$n=ab^2,$$

avec $a$ produit de nombres premiers distincts. Préciser un choix de $a$ et $b$ lorsque $n=1$.

II — Un choix binaire par nombre premier

Supposons maintenant, par l'absurde, qu'il n'existe qu'un nombre fini de nombres premiers. On les note

$$p_1,p_2,\ldots,p_r,$$

où $r\ge 1$.

(a) À tout mot $(\varepsilon_1,\ldots,\varepsilon_r)$ de longueur $r$ formé de $0$ et de $1$, on associe

$$A(\varepsilon_1,\ldots,\varepsilon_r) =p_1^{\varepsilon_1}\cdots p_r^{\varepsilon_r}.$$

Expliquer pourquoi toute valeur de $a$ obtenue dans la partie I est la valeur de $A$ pour au moins un tel mot. Que donne le mot $(0,\ldots,0)$ ?

(b) Combien existe-t-il de mots de longueur $r$ formés de $0$ et de $1$ ? En déduire qu'il existe au plus $2^r$ valeurs possibles pour $a$.

III — Combien d'entiers peut-on alors fabriquer ?

On fixe un entier $N\ge 1$. Sous l'hypothèse précédente, chacun des entiers $1,2,\ldots,N$ possède une écriture $n=ab^2$ construite comme dans la partie I.

(a) Si $n=ab^2\le N$ avec $a\ge 1$, montrer que $b\le \sqrt N$.

(b) En déduire qu'il existe au plus $\lfloor\sqrt N\rfloor$ valeurs possibles pour l'entier positif $b$.

(a) À l'aide du principe multiplicatif, donner une majoration du nombre de couples $(a,b)$ susceptibles d'intervenir pour représenter des entiers compris entre $1$ et $N$.

(b) Deux couples différents pourraient, a priori, donner le même entier. Expliquer pourquoi cette éventuelle coïncidence ne peut qu'abaisser le nombre d'entiers distincts obtenus, et ne remet donc pas en cause la majoration précédente.

(c) Tous les entiers $1,2,\ldots,N$ devant être représentés, établir la condition nécessaire

$$N\le 2^r\lfloor\sqrt N\rfloor\le 2^r\sqrt N.$$

IV — Choisir une borne qui fait craquer l'hypothèse

6. On cherche désormais $N$ parmi les carrés parfaits. Écrire $N=M^2$ avec $M$ entier strictement positif. Déterminer une condition simple sur $M$ qui assure

$$N>2^r\sqrt N,$$

puis proposer un choix explicite et aussi simple que possible de $M$, et donc de $N$, en fonction de $r$.

V — Trop d'entiers

7. Pour la valeur de $N$ choisie à la question 6, comparer précisément le nombre $N$ d'entiers

$$1,2,\ldots,N$$

avec le nombre maximal de couples $(a,b)$ disponibles. Faire apparaître la contradiction, puis conclure sur le nombre de nombres premiers.

Le mécanisme découvert ici est entièrement global : aucun nouveau nombre premier n'a été construit. Sous l'hypothèse d'un stock fini de nombres premiers, il n'existerait que trop peu de choix binaires pour les facteurs laissés hors du carré, puis trop peu de couples $(a,b)$ pour fabriquer tous les entiers.