Polynômes à valeurs entières

Les mathématiciens disent : « un polynôme qui produit… des valeurs entières, des valeurs premières… ». Ce vocabulaire est tout à fait pertinent et on peut poursuivre l'analogie industrielle : nous sommes dans une usine, on prend une machine, pardon un polynôme P, on « entre » un entier x, on fabrique la valeur P(x) et on la « sort », ou bien on appuie sur la touche "N" et on « sort » la suite P(0), P(1), P(2), P(3), P(4), P(5), P(6), etc.

Si vous savez ce qu'est un polynôme, pas de problème. Si vous ne savez pas, imaginez une machine du genre : on « entre » un nombre (pour nous ce sera un entier, mais ce n'est pas obligatoire), on le multiplie par 7, on ajoute 31, et on « sort » le résultat – ou bien : on « entre » un nombre, on l'élève au carré, on ajoute 1, et on « sort » le résultat. Le nombre entré, appelé la variable, est traditionnellement noté x, et le résultat, appelé la valeur (ou la valeur prise), est noté P(x).

Il faut savoir que la machine, pardon un polynôme P, possède des boutons de réglage pour la fabrication, avec ce que les mathématiciens appellent le degré et les coefficients du polynôme. L'ingénieur, pardon le mathématicien, se fixe des objectifs précis sur le résultat : il veut des valeurs qui soient des nombres entiers, des nombres premiers, il veut des diviseurs obligatoires, ou au contraire interdits... Alors il va tourner les boutons de réglage, pour tenter de maîtriser ce qui sort. Il peut aussi arriver qu'il tourne les boutons au hasard, et voie de temps en temps une production inattendue, alors il faut essayer de comprendre, on appelle l'expert, il arrive avec sa sacoche pleine de théorèmes, on essaie de trouver celui ou ceux qui marchent, ceux qui expliquent, qui améliorent la maîtrise de la production…

Avant de faire la visite guidée de l'usine, il faut énoncer une exigence absolue : on peut régler les polynômes comme on veut, degré, coefficients – par contre la variable sera toujours un entier (relatif) ; quand on dira par exemple « le polynôme P ne produit que des entiers », cela veut dire que la suite infinie (aux deux bouts)

…, P(–n), …, P(–3), P(–2), P(–1), P(0), P(1), P(2), P(3), …, P(n), …

L'usine des polynômes est un fournisseur attitré et important de l'usine voisine des comptes et des sommes. Des exemples.

Au fait, quels sont les polynômes qui ne produisent que des entiers (pour les valeurs entières de la variable, redisons-le) ?

Les polynômes à coefficients entiers bien sûr, 24 x + 7 ou x² + 1 ou xⁿ – x.
Mais aussi des polynômes à coefficients rationnels non tous entiers,

Étant donné un polynôme à coefficients entiers, il peut arriver qu'il soit toujours (sous-entendu : pour les valeurs entières de la variable) divisible par un certain entier k. Si tous les coefficients du polynôme sont divisibles par k, alors k est un diviseur « apparent » du polynôme. Mais il se peut aussi que k soit un diviseur « caché » ...

Et pourquoi le polynôme x(x – 1)(x – 2) est-il toujours divisible par 6 ?

Même type de réponse, mais en plus compliqué : parce qu'il est à fois toujours divisible par 2 et toujours divisible par 3. Par 2, pour la même raison que pour le précédent, et par 3, encore pour la même raison : l'un des trois entiers consécutifs x, x – 1 et x – 2 est divisible par 3.

Vous avez tout compris, alors dites-moi maintenant pourquoi le polynôme x⁵ – x est toujours divisible par 5 ?

Tout n'est pas encore clair mais on peut quand même progresser un peu, notamment en "mariant" plusieurs divisibilités : si u et v sont premiers entre eux, la divisibilité d'un entier par uv est équivalente à la conjonction de la divisibilité par u et de la divisibilité par v ("conjonction" = à la fois l'un et l'autre).

Est-ce que cela va de soi ? Le « théorème de Gauss » dit que, étant donnés trois entiers a, b et c (non nuls), si a divise le produit bc et est premier avec b, alors il divise c.

Corollaire du théorème de Gauss : si deux entiers u et v premiers entre eux divisent un entier w, alors leur produit uv divise w (démonstration : comme u divise w, on peut écrire w = uz, mais v divise w = uz et est premier avec u, donc il divise z, gagné !)

La divisibilité d'un entier par uv, disions-nous donc, est équivalente si u et v sont premiers entre eux à la conjonction de la divisibilité par u et de la divisibilité par v. Par conséquent, pour étudier la divisibilité des valeurs d'un polynôme par un entier d, il est nécessaire et suffisant d'étudier la divisibilité par les facteurs « primaires » de d : si par exemple d = p^aq^br^c (p, q, r premiers), on étudiera la divisiblité par p^a et par q^b et par r^c.

Attention ! Attention ! Dans le théorème de Gauss, dans son corollaire et dans tout ce qui va suivre, les entiers sont relatifs, et par exemple 19 et –19 sont tous les deux des nombres premiers.

Une vérification numérique n'est pas une démonstration, et de toute façon, à x = 8, on est encore loin de l'infini ! Il nous faut un théorème, le voilà :

THÉORÈME A

Soit P un polynôme à coefficients entiers, et M un nombre entier. Alors, pour tout entier x et tout entier k

P(x + kM) ≡ P(x) (mod. M).

En particulier, si P(x) est divisible par M, tous les P(x + kM) sont divisibles par M.

Utilisation n° 1 de ce théorème, démonstration que P(x) = x⁵ – x est toujours divisible par 5, avec M = 5 : P(0) et P(1) et P(2) et P(3) et P(4), sont divisibles par 5, et tout entier est de la forme x + 5k avec x = 0 ou 1 ou 2 ou 3 ou 4. Mais c'est une démonstration qui ne fait que démontrer dans le cas particulier de ce polynôme. Il y aura plus tard une explication, et cette explication sera générale.

x⁵ – x = x (x – 1) (x – 2) (x – 3) (x – 4) + 5 x (x – 1) (2x² – 5x + 5).

Cela donne une vraie démonstration, mais malheureusement elle ne se généralise pas bien.

Utilisation n° 2 de ce théorème, démonstration qu'il n'y a aucun polynôme (non constant) qui ne donne que des nombres premiers.

On prend un entier x quelconque (0 par exemple !) et on considère P(x) = y. Si l'entier y n'est pas premier, le polynôme P aura pris (au moins) une valeur composée et la démonstration est terminée. Si y = p premier (positif ou négatif, peu importe), on considère l'ensemble infini des P(x + kp) pour k appartenant à Z. D'après le théorème A (pour M = p), tous ces P(x + kp) sont divisibles par p. Un théorème (un autre… nous ne le démontrerons pas ici – il est d'ailleurs intuitivement évident) dit qu'un polynôme (non constant) ne peut pas prendre une infinité de fois la même valeur : donc les valeurs P(x + kp) ne peuvent pas toutes être égales à p ou à –p… et il y en a donc une qui est composée (il y en a en fait une infinité).

Il n'y a aucun polynôme (non constant) qui ne donne que des nombres premiers. Au cas où l'on aurait la naïveté de rechercher une « formule » qui ne donnerait que des nombres premiers, on voit tout de suite qu'une telle formule doit être plus compliquée qu'une formule polynomiale (au cas où la question vous intéresserait, sachez qu'il existe de telles formules – très très compliquées –, mais qu'aucune ne peut servir en pratique, ni pour « fournir » la liste des nombres premiers, ni même pour fournir seulement une suite de grands nombres premiers...).

Si vous y tenez…! Mais il faut d'abord connaître la « formule du binôme » et aussi les coefficients « binomiaux ».

vous avez bien dû rencontrer ça une fois dans votre vie ? Et la suite ? Vous avez deviné :

s'appellent les coefficients binomiaux et il suffit de savoir que ce sont des entiers. Prenez maintenant a = x et b = k M :

Le premier terme est xⁿ, et chacun des termes suivants est le produit d'un coefficient binomial (un entier) par une puissance de x (un entier) par une puissance de kM d'exposant ≥ 1 (donc un entier divisible par M). Conclusion : (x + k M)ⁿ ≡ xⁿ (mod. M).

Chaque nombre sur chaque ligne est la somme des deux qui sont au-dessus, juste à gauche et juste à droite (sauf pour les bords, encore qu'il suffise d'imaginer des "0" là où il n'y a rien pour que la règle soit générale).

Et secundo, vous avez remarqué ? Pour le degré 3, tous les coefficients sauf les extrêmes (égaux à 1) sont divisibles par 3, pour le degré 5, tous les coefficients sauf les extrêmes (égaux à 1) sont divisibles par 5, pour le degré 7, tous les coefficients sauf les extrêmes (égaux à 1) sont divisibles par 7, pour le degré 11, … calculez–les donc et voyez ! A noter que cette propriété n'est vraie que pour les degrés qui sont des nombres premiers.

Encore un théorème : si vous connaissez la formule qui donne les coefficients binomiaux
pour les initiés – cette formule est en lien direct avec le triangle arithmétique de Pascal, mais c'est une autre histoire...–, vous pouvez démontrer que pour un degré n = p premier, tous les coefficients sauf les extrêmes sont divisibles par p. Pour tout k tel que 1 ≤ k ≤ p – 1, le numérateur de la formule est divisible par p, et le dénominateur, produit de facteurs tous inférieurs à p donc tous premiers avec p, n'est pas divisible par p (encore le théorème de Gauss !).

Toutes les démonstrations en arithmétique – celle du petit théorème de Fermat comme les autres – utilisent le théorème de Gauss. Mais il y a un petit problème... Fermat (1601–1665) a vécu presque deux siècles avant Gauss (1777–1855)... Alors ? Si ce petit point d'histoire des mathématiques vous intéresse, cliquez ici (mais ce n'est pas obligatoire pour comprendre la suite).

LEMME

Soit p un nombre premier. Alors, pour tous entiers a et b

(a + b)^p ≡ a^p + b^p (mod. p).

Quand un énoncé est vrai, les mathématiciens ont l'habitude de l'appeler théorème (ou proposition) s'il présente un intérêt en soi, et lemme s'il n'a pas d'autre intérêt que d'être utilisé pour démontrer un théorème. Sans oublier bien sûr les corollaires, qui sont des conséquences plus ou moins immédiates d'un théorème.

Démonstration du lemme : on écrit la formule du binôme pour n = p premier :

Tous les termes du développement autres que les termes extrêmes sont divisibles par p, ce qui donne la formule du lemme.

THÉORÈME B (petit théorème de Fermat)

Soit p un nombre premier. Alors, pour tout entier x : x^p ≡ x (mod. p).

Autre formulation, équivalente bien sûr :

Soit p un nombre premier. Alors, pour tout entier x non divisible par p

x^p–1 ≡ 1 (mod. p).

On peut imaginer beaucoup de démonstrations du petit théorème de Fermat. En voici une, basée sur la formule (a + b)^p ≡ a^p + b^p (mod. p) du lemme précédent :

Pour les esprits curieux et familiers de la manipulation des congruences, on peut donner une autre démonstration.

Le petit théorème de Fermat possède un très grand nombre d'applications. Pour ce qui nous concerne (les polynômes), il nous explique pourquoi P(x) = x⁵ – x est toujours divisible par 5, en nous montrant que c'est une propriété arithmétique (et non pas algébrique) générale (et non pas particulière au degré 5).

Et si l'exposant n'est pas un nombre premier ? Cela nous entraînerait trop loin, en direction de l'« indicateur d'Euler ». Pour les courageux, je leur propose de démontrer

Qui « donnent … », qui « fournissent … », qui « produisent … », toutes ces expressions sont synonymes.

P(0) = 41 est un nombre premier, P(1) = 43 est un nombre premier, P(2) = 47 est un nombre premier, P(3) = 53 est un nombre premier, P(4) = 61 est un nombre premier, P(5) = 71 est un nombre premier, P(6) = 83 est un nombre premier, P(7) = 97 est un nombre premier, P(8) = 113 est un nombre premier, P(9) = 131 est un nombre premier, etc.

Et cœtera, ça veut dire quoi ? Que toutes les valeurs prises par x² + x + 41 sont des nombres premiers ? … oui ? Vous avez perdu !! Il n'y a pas un seul polynôme qui ne donne que des valeurs premières (pour les valeurs entières de la variable, redisons-le encore). Nous l'avons déjà remarqué mais vous n'avez peut-être pas prêté suffisamment attention au passage : c'était le corollaire (appelé « utilisation n° 2 ») du théorème A.

Alors, finalement, le polynôme d'Euler ? Quarante nombres premiers consécutifs, de x = 0 à x = 39. Vous pouvez vérifier… Et vous pouvez aussi vérifier que

n'est pas premier. Les petits malins remarqueront que P(–1) = P(0), P(–2) = P(1), …,
P(–40) = P(39), de sorte que le polynôme d'Euler fournit en réalité 80 nombres premiers, de x = –40 à x = 39. Mais ce n'est que du bégaiement, tous les nombres premiers sont donnés deux fois, alors on interdit cela dans la règle du jeu.

Peut-on faire mieux qu'Euler ? La réponse est oui mais il a fallu attendre 1988 pour détrôner ce record : Fung a trouvé le polynôme 47 x² + 9 x – 5 209, qui fournit 43 nombres premiers consécutifs, de x = –22 à x = –18. Une remarque : l'expression "40 (ou 43) nombres premiers consécutifs" ne signifient pas qu'ils soient consécutifs dans la suite des nombres premiers mais que 40 (ou 43) valeurs du polynôme, obtenues pour 40 (ou 43) valeurs consécutives de la variable, sont des nombres premiers. Ce record a été battu l'année suivante par Ruby, avec le polynôme 36 x² + 18 x – 1 801, qui fournit 45 nombres premiers consécutifs, de x = –33 à x = 11.

Le polynôme 16 x⁴ + 28 x³ – 1 685 x² – 23 807 x + 110 647, trouvé en 2000 par Dress et Landreau, fournit 46 nombres premiers consécutifs, de x = –23 à x = 22. Comment fait-on pour trouver un tel polynôme ?

On essaye tous les polynômes a₀x⁴ + a₁x³ + a₂x² + a₃x + a₄, avec par exemple |a₀| ≤ 50, |a₁| ≤ 500, |a₂| ≤ 5 000, |a₃| ≤ 50 000 et |a₄| ≤ 500 000, et on teste la « primalité » de leurs valeurs entre x = –100 et x = 100. Très mauvaise réponse !! Cela fait 101 ∙ 1 001 ∙ 10 001 ∙ 100 001 ∙ 1 000 001 ≈ 1,011 · 10²⁰ polynômes à 201 valeurs chacun, soit environ 2,032 · 10²² valeurs à calculer et à tester. Si vous mettez à 1 microseconde le temps de calcul et de test pour une valeur (ce n'est pas surestimé !), vous obtenez environ 2,032 · 10¹⁶ secondes ≈ 2,352 · 10¹¹ jours ≈ 644 millions d'années.

Alors… la bonne réponse ? Ne tester qu'un infime partie des polynômes, en éliminant ceux qui sont des mauvais candidats parce qu'ils ont trop de « petits » diviseurs premiers périodiques. Si vous arrivez à éliminer 99.9999999 % des polynômes, c'est gagné ! … vous avez dit diviseurs premiers périodiques ?

Nous allons tout expliquer sur un exemple. Considérons un polynôme très simple et ressemblant au polynôme d'Euler, par exemple P₇(x) = x² + x + 7, et étudions sa divisibilité par les nombres premiers successifs 2, 3, 5, 7, 11, 13, ... Rappelons-nous le théorème A, il nous dit que nous saurons tout sur la divisibilité par p (premier) si nous regardons ce qui se passe pour p valeurs consécutives de la variable, par exemple P(0), P(1), P(2), ..., P(p–1).

P₇ n'est jamais divisible par 2, on dit que 2 n'est pas un diviseur premier périodique de P₇.

P₇(0) = 7 non congru à 0, P₇(1) = 9 ≡ 0, P₇(2) = 13 non congru à 0 (mod. 3) :

P₇ est parfois divisible par 3 (1 fois sur 3), on dit que 3 est un diviseur premier périodique de P₇.

P₇(0) = 7 non congru à 0, P₇(1) = 9 non congru à 0 , P₇(2) = 13 non congru à 0, P₇(3) = 19 non congru à 0 , P₇(4) = 27 non congru à 0 (mod. 5) :

P₇ n'est jamais divisible par 5, on dit que 5 n'est pas un diviseur premier périodique de P₇.

P₇(0) = 7 ≡ 0, P₇(1) = 9 non congru à 0, ..., P₇(5) = 37 non congru à 0, P₇(6) = 49 ≡ 0 (mod. 7) :

P₇ est parfois divisible par 7 (2 fois sur 7), on dit que 7 est un diviseur premier périodique de P₇.

On peut faire un petit programme pour rechercher les diviseurs premiers périodiques. Pour P₇(x) = x² + x + 7, on obtient 3, 7, 13, 19, 31, 37, 43, 61, 67, 73, 79, 97, ... et, a contrario, pas 2, pas 5, pas 11, pas 17, pas 23, pas 29, pas 41, ...

Comment peut-on se servir des diviseurs premiers périodiques pour rechercher des polynômes record ? Encore un exemple... Oublions un instant le polynôme d'Euler avec ses 40 valeurs premières consécutives, et imaginons que nous recherchons modestement 10 valeurs premières consécutives. La méthode empirique est la suivante, étant donné un polynôme P, on regarde combien il y a de nombres premiers sur les 50 (50, pas 10) valeurs P(0), P(1), P(2), ..., P(49). S'il y en a beaucoup, il y a des chances d'en trouver 10 consécutives, s'il y en a peu, il n'y a quasiment aucune chance.

diviseurs premiers périodiques de P₁₇ : 17, 19, 23, 29, 37, 47, 59, 67, 71, 73, 83, ...

diviseurs premiers périodiques de P₁₉ : 3, 5, 7, 13, 19, 31, 37, 43, 61, 67, 73, 79, ...

P₁₇ est un bon polynôme : aucun diviseur premier avant 17. P₁₉ est une catastrophe : 1 valeur sur 3 sera divisible par 3, 2 sur 5 divisibles par 5, 2 sur 7 divisibles par 7, 2 sur 13 divisibles par 13, etc. Vérification :

Voilà donc le principe : pour rechercher des polynômes record, on écrit un programme informatique qui utilise un « crible » sur les diviseurs premiers périodiques de façon à ne tester que des polynômes n'ayant que des "grands" diviseurs premiers périodiques. Principe simple, mise en œuvre délicate... et finalement des durées de calcul entre quelques semaines et quelques mois sur des « stations de travail » super–rapides !

On ne trouvera vraisemblablement jamais de polynôme du deuxième degré qui dépasse 45 (Ruby). Par contre, il y a 8 polynômes de degré 4 qui fournissent 46 nombres premiers consécutifs, le plus simple est celui déjà donné plus haut
16 x⁴ + 28 x³ – 1 685 x² – 23 807 x + 110 647, de x = –23 à x = 22 (Dress et Landreau, Bordeaux, 2000). On a également trouvé un polynôme de degré 3 qui fournit 46 nombres premiers consécutifs : 66 x³ + 83 x² – 13 735 x + 30 139, de x = –26 à x = 19 (Dress et Landreau, Bordeaux, 2001).

Souvenez-vous maintenant du début, il n'y a pas que les polynômes à coefficients entiers qui ne produisent que des entiers (pour les valeurs entières de la variable), il y a aussi des polynômes à coefficients rationnels non tous entiers. Pour des raisons qu'il serait trop compliqué d'expliquer, il n'y a aucune chance d'en trouver en degrés 2 ou 3. A nous les degrés supérieurs !

fournit 57 valeurs premières pour 57 valeurs consécutives de la variable, de x = –27 à
x = 29 (Dress et Landreau, Bordeaux, 2003).

On peut qualifier les records précédents de records "n sur n", mais il y a aussi des records "k sur n" (avec k < n). Par exemple le polynôme 41 x² + 33 x – 43 321 : 90 valeurs premières sur 100 valeurs consécutives de la variable, de x = –57 à x = 42 (Boston et Greenwood, 1995), et le polynôme x² + x – 1 354 363 (Dress et Olivier, Bordeaux, 1998) : 698 valeurs premières (différentes) sur 1 000 valeurs consécutives de la variable, de x = 1 139 à x = 2 138.