×

Some remarks on a number theoretic problem of Graham. (English) Zbl 0313.10002

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

MSC:

11A05 Multiplicative structure; Euclidean algorithm; greatest common divisors

Citations:

Zbl 0192.33202
PDFBibTeX XMLCite
Full Text: DOI EuDML