Les nombres premiers ! 25 000 ans après avoir été découvert, 2 300 ans après avoir été étudiés et 30 ans après leur avoir trouvé une utilité dans la vie de tous les jours (la fameuse "utilité" des mathématiques...), les nombres premiers sont une source inépuisable de conjectures et de théorèmes !
Très présents dans les recherches actuelles, les énoncés sur lesquels les mathématiciens se cassent la tête ont souvent la particularité d'être d'une simplicité déconcertante (Je ne classe pas l'hypothèse de Riemann comme un énoncé simple).

Aujourd'hui, donc, un petit article à propos de ces 26 nombres premiers que l'on ne peut pas rater, les "nombres premiers inévitables" !

Jeffrey Shallit (informaticien et théoricien des nombres) a introduit le concept des nombres inévitables. Dans le mot "CHOUXROMANESCO", on peut par exemple retrouver le mot "CRANE", lorsque l'on enlève certaines lettres. On peut dire que le mot "CRANE" est inclus dans le mot "CHOUXROMANESCO" (en ne touchant pas à l'ordre des lettres).
Si on peut le faire avec des lettres, on peut le faire avec des chiffres : par exemple, un nombre tel que 198432 contient (entre autres) les nombres 184, 983 ou 42.
Pour un nombre premier donné, on peut se poser la question des nombres premiers qui y sont inclus. Prenons 19843, qui est premier. Il contient les nombres 3, 13, 19, 43, 83, 193 et 983 qui sont premiers. Dans le nombre premier 946649, par contre, il n'y a aucun "sous-nombre" qui soit premier.

La question que s'est posé Shallit (en 1996) était de savoir si il existe une famille (finie) de nombres premiers tel que tout nombre premier contienne l'un des nombre de cette famille (ou en fasse partie). De manière équivalente, on peut se demander si il existe un nombre infini de nombre comme 946649 qui ne contiennent aucun autres nombres premiers.

La réponse fut apportée rapidement par Lothaire (en 1983, avant que Shallit ne se pose la question, en fait...), avec un théorème de la théorie des langages formels (la théorie mathématique qui étudie les ensembles de chaînes de caractères (ou "motifs")). Ce théorème dit que si on prend un ensemble infini de motifs, il existera toujours un de ces motifs qui sera inclus dans un autre.
Appliqué à la question de Shallit, (ici, les "motifs" sont les nombres écrits en base 10), on peut conclure qu'il existe bien un nombre fini de nombres premiers que l'on retrouve dans n'importe quel autre nombre premier. Ces nombres sont appelés "nombres premiers inévitables". (On peut dire la même chose de n'importe quel ensemble de nombres)

Nouvelle question alors : quels sont ces nombres ?
Un algorithme nous donne la solution : L'idée pour les trouver tous est de passer en revue tous les nombres premiers, et de ne garder que ceux qui n'en contiennent pas d'autre :

2 : on garde
3 : on garde
5 : on garde
7 : on garde
11 : on garde
13 : on ne garde pas, il contient 3
17 : on ne garde pas, il contient 7
19 : on garde
23 : on ne garde pas, il contient 2 et 3

Et ainsi de suite. On sait que l'ensemble des nombres que l'on va garder, les "nombres premiers inévitables" est fini, donc on devrait les avoir tous au bout d'un certain temps grâce à cet algorithme...
Reste à savoir quand il faut s'arrêter de tester les nombres de l'ensemble... En fait, on ne peut pas savoir quand l'arrêter : ce n'est pas parce que l'ordinateur ne trouve pas de nouveaux nombres inévitables qu'il n'en existe pas d'autres très grands.

Pour les trouver tous, il faut donc procéder autrement, et raisonner plutôt que de chercher à la brutale.
L'exemple simple est celui des nombres pairs : il est facile de voir que l'ensemble {0,2,4,6,8} est l'ensemble des nombres pairs inévitables, puisque tous les nombres pairs finissent par l'un de ces chiffres. En associant le raisonnement et la méthode algorithmique, on peut trouver les multiples de 4 inévitables : ils sont forcément inférieurs à 100 (un nombre est divisible par 4 si ses deux derniers chiffres forment un nombre divisible par 4), et l'algorithme permet de trouver que ces nombres sont {0, 4, 8, 12, 16, 32, 36, 52, 56, 72, 76, 92, 96}.

Le raisonnement est beaucoup plus compliqué pour celui des nombres premiers, mais Shallit l'a fait pour nous. On connait alors la liste des nombres premiers inévitables :

{2, 3, 5, 7,
11, 19, 41, 61, 89,
409, 449, 499, 881, 991,
6469, 6949, 9001, 9049, 9649, 9949,
60649,
666649, 946649,
60000049, 66000049, 66600049}

L'utilité de cette découverte à propos des nombres premiers reste essentiellement esthétique ! Ces 26 nombres premiers ressortent "miraculeusement" du lot de tous les nombres premiers (pour nous, qui voyons le monde en base 10).
On voit quand même qu'il n'y en a pas entre 1 000 000 et 60 000 000, on aurait pu oublier les 3 derniers avec la méthode algorithmique en l'arrêtant trop tôt !

 

Petit jeu !
Parmi les propositions suivantes, saurez-vous trouver celles que l'on ne sait pas démontrer ?
1 - L'ensemble des entiers inévitables est {0,1,2,3,4,5,6,7,8,9}
2 - L'ensemble des nombres premiers écrits en base 2 inévitables est {10, 11}
3 - L'ensemble des puissances de 2 inévitables est {1,2,4,8,65536}
4 - L'ensemble des nombres non-premiers inévitable est { 4, 6, 8, 9, 10, 12, 15, 20, 21, 22, 25, 27, 30, 32, 33, 35, 50, 51, 52, 55, 57, 70 72, 75, 77, 111, 117, 171, 371, 711, 713, 731}
5 - L'ensemble des nombres divisibles par 3 inévitables est {0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 42, 45, 48, 51, 54, 57, 72, 75, 78, 81, 84, 87, 111, 114, 117, 141, 144, 147, 171, 174, 177, 222, 225, 228, 252, 255, 258, 282, 285, 288, 411, 414, 417, 441, 444, 447, 471, 474, 477, 522, 525, 528, 552, 555, 558, 582, 585, 588, 711, 714, 717, 741, 744, 747, 751, 774, 777, 822, 825, 828, 852, 855, 858, 882, 885, 888}
6 - L'ensemble des nombres de la suite de Fibonacci inévitable est {0, 1, 2, 3, 5, 8}

Solution :
1 - Démontré ! Evident, en fait...
2 - Démontré ! Evident aussi : tout nombre supérieur à 2 écrit en base 2 commence par "10" ou "11". Ces deux nombres étant premiers, ils sont inévitables.
3 - Conjecture ! (encore par Shallit)
4 - Démontré ! (encore par le même)
5 - Démontré ! Il faut voir par le raisonnement qu'un inévitable ne peut être plus grand que 1000 (le raisonnement n'est pas compliqué - arithmétique de lycée)
6 - Conjecture de moi ! (Faut dire que j'ai pas vraiment cherché à le démontrer, en fait... Peut-être est-ce déjà un théorème ?)


Sources :
Pour la science - n°296 (Juin 2002) - Nombres premiers inévitables et pyramidaux (Contient la démonstration de la proposition n°5)