Nombre d'Erdős-Woods

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En théorie des nombres, un nombre d'Erdős-Woods est un entier naturel k > 1 tel qu'il existe k + 1 entiers strictement positifs consécutifs dont chacun a un facteur commun avec le premier ou le dernier.

Les trois premiers nombres d'Erdős-Woods sont 16, 22 et 34 (suite A059756 de l'OEIS) et les plus petites valeurs de points initiaux correspondants sont 2184, 3 521 210 et 47 563 752 566 (suite A059757).

Les recherches sur ces nombres viennent de la conjecture suivante d'Erdős[1] :

Il existe un entier k > 1 tel que pour tous entiers a > 1 et b > a + k, PPCM(a, a + 1, …, a + k) et PPCM(b, b + 1, …, b + k) n'ont pas les mêmes facteurs premiers.

Alan R. Woods a étudié cette question dans sa thèse de Ph.D. en logique mathématique sur des problèmes de définissabilité[2], où il conjecturait que pour tout k > 1, l'intervalle [a, a + k] contient toujours un nombre premier avec chacune des deux extrémités. Ce n'est que par la suite qu'il découvrit le premier contre-exemple, [2184, 2185, …, 2200], avec k = 16.

David Dowe a démontré qu'il existe une infinité de nombres d'Erdős-Woods[3] et Cégielski, Heroult et Richard, que l'ensemble de ces nombres est récursif[4].

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Erdős–Woods number » (voir la liste des auteurs).

  1. (en) P. Erdős, « How many pairs of products of consecutive integers have the same prime factors? (Research problem) », Amer. Math. Month., vol. 87,‎ 1980, p. 391-392 (lire en ligne)
  2. (en) Alan Robert Woods, Some problems in logic and number theory, and their connections, Univ. Manchester,‎ 1981 (lire en ligne)
  3. (en) David L. Dowe, « On the existence of sequences of co-prime pairs of integers », J. Austral. Math. Soc., Series A, vol. 47,‎ 1989, p. 84-89 (lire en ligne)
  4. (en) Patrick Cégielski, François Heroult et Denis Richard, « On the amplitude of intervals of natural numbers whose every element has a common prime divisor with at least an extremity », TCS (en), vol. 303, no 1,‎ 2003, p. 53-62 (DOI 10.1016/S0304-3975(02)00444-9)