Nombre d'Erdős-Woods

Page d’aide sur l’homonymie

Ne pas confondre avec la notion de nombre d'Erdős ou celle de nombre d'Erdős–Nicolas.

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 2 184, 3 521 210 et 47 563 752 566 (suite OEIS 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 doctorat 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

(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,‎ , p. 391-392 (lire en ligne)
  2. ↑ (en) Alan Robert Woods, Some problems in logic and number theory, and their connections, Univ. Manchester, (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,‎ , 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, vol. 303, no 1,‎ , p. 53-62 (DOI 10.1016/S0304-3975(02)00444-9)