Nombre d'Erdős-Woods

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

(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).

(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)
(en) Alan Robert Woods, Some problems in logic and number theory, and their connections, Univ. Manchester, 1981 (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,‎ 1989, 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, n^o 1,‎ 2003, p. 53-62 (DOI 10.1016/S0304-3975(02)00444-9)

Arithmétique et théorie des nombres

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[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, vol. 303, n^o 1,‎ 2003, p. 53-62 (DOI 10.1016/S0304-3975(02)00444-9)