Nombre d'Erdős-Woods
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 
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
[modifier | modifier le code]- (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)
- (en) Alan Robert Woods, Some problems in logic and number theory, and their connections, Univ. Manchester, (lire en ligne)
- (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)
- (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)
