Vélez, William Yslas Some remarks on a number theoretic problem of Graham. (English) Zbl 0313.10002 Acta Arith. 32, 233-238 (1977). R. L. Graham has made the following conjectures for sequences of positive integers \(0<a_1<a_2<\ldots<a_n\). In the following \((\alpha_1,\alpha_2,\ldots,\alpha_n)\) denotes the gcd of \(\{\alpha_1,\alpha_2,\ldots,\alpha_k\}\).Conjecture 1. If \(0<a_1<\ldots<a_n\), then \[ \max_{i,j} \frac{a_i}{(a_i,a_j)}\geq n. \]The conjecture has been verified in some special cases (i) \(a_i\) is squarefree for all \(i\) [J. Marica and J. Schönheim, Can. Math. Bull. 12, 635–637 (1969; Zbl 0192.33202)], (ii) \(a_i\) is prime [R. Winterle, Proc. Louisiana Conf. on Combinatorics, Graph Theory and Computing, Baton Rouge, La., 1970, 357–361 (1970)], and (iii) \(n\) is prime [Szemerédi]. Conjecture 2. If \(0<a_1<\ldots<a_n\), \((0,a_1,a_2,\ldots,a_n=1\) and \(\max_{i,j} \frac{a_i}{(a_i,a_j)}=n\), then either \(a_i=i\) for all \(i\), or \(a_i=M/(n-i+1)\), for all \(i\) where \(M= \text{lcm}\{1,2,\ldots,n\}\), except when \(n=4\), where we have the additional sequence \(2<3<4<6\).In this paper we prove, among other things, that (a) Conjecture 2 implies Conjecture 1, and (b) Conjecture (2) is true when \(n=p\), \(p\) a prime. Reviewer: W. Y. Vélez Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 5 Documents MSC: 11A05 Multiplicative structure; Euclidean algorithm; greatest common divisors Citations:Zbl 0192.33202 PDFBibTeX XMLCite \textit{W. Y. Vélez}, Acta Arith. 32, 233--238 (1977; Zbl 0313.10002) Full Text: DOI EuDML