Exercice 1 — Énoncé — Olympiades 2010 Dijon

Sujet

Nombres quasi-premiers

On rappelle qu'un entier naturel est premier s'il possède exactement deux diviseurs positifs. La liste des nombres premiers commence ainsi : \(2,3,5,7,11,13,17,19,23, \ldots\), et cette liste est infinie.
On dit qu'un nombre entier naturel non nul est un nombre quasi-premier si ce nombre n'est pas premier et si, en modifiant un et un seul des chiffres de l'écriture en base dix de ce nombre, on obtient un nombre premier.
Par exemple 24 est un nombre quasi-premier car il n'est pas premier et 23 est premier.

Quelques exemples
a) Démontrer que tout entier non nul inférieur à 100 est soit premier, soit quasi-premier.
b) Quelle est la nature du nombre 100 ?
Démontrer qu'il existe une infinité de nombres quasi-premiers.
Encore des infinités
a) Démontrer que le nombre 200 n'est ni premier ni quasi-premier.
b) Soit \(k\) un entier naturel. Le nombre \(2310 k+200\) peut-il être premier? Peut-il être quasipremier?
c) En déduire qu'il existe une infinité de nombres qui ne sont ni premiers ni quasi-premiers.
Des nombres à la chaîne
a) Peut-on trouver une liste de 7 entiers consécutifs qui soient des nombres quasi-premiers?
b) Peut-on trouver une telle liste de longueur supérieure à 7 formée uniquement de nombres quasi-premiers?

Commençons par prolonger la liste des nombres premiers jusqu'à 127 en utilisant le crible d'Eratosthène : \(\ldots, 23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127, \ldots\)

a. Toute dizaine inférieure à 100 contient un nombre premier.

Soit \(n=10 a+b\) avec \(0 \leqslant a \leqslant 9\) et \(0 \leqslant b \leqslant 9\); ou bien \(n\) est premier, ou bien il existe \(b^{\prime} \neq b\) tel que \(10 a+b^{\prime}\) soit premier et donc que \(n\) soit quasi-premier.
b. 100 est quasi-premier car il n'est pas premier mais 1201 l'est.
2. A tout nombre premier \(p\) différent de 2 , associons un nombre \(p^{\prime}\) obtenu en remplaçant le chiffre des unités par un chiffre pair.
\(p^{\prime}\) qui est pair n'est pas premier, mais il est quasi-premier car \(p\) qui diffère de \(p^{\prime}\) par le chiffre des unités est premier.

Comme on a cinq choix possibles pour le chiffre des unités de \(n^{\prime}\) et que la table montre qu'il y a au maximum quatre nombres premiers par dizaine, on établit ainsi une injection de l'ensemble infini des nombres premiers dans l'ensemble des quasi-premiers; celui-ci est donc de cardiinal infini.
3. a. 200 n'est pas premier car divible par \(2,5,8,10\) et 20 . Il n'est pas quasi-premier car en modifiant un de ses chiffres autre que celui des unités, on obtient un multiple de 10 et en modifiant le chiffre des unités, on obtient \(201,202, \ldots 209\) qui ne sont pas premiers car :

202, 204, 206 et 208 sont pairs
201, 204 et 207 sont multiples de 3
205 est multiple de 5
et 209 multiple de 11 .