Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 

 

On a conjecture of Graham concerning greatest common divisors


Author: Gerald Weinstein
Journal: Proc. Amer. Math. Soc. 63 (1977), 33-38
MSC: Primary 10A25
MathSciNet review: 0434941
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ {a_1} < {a_2} < \cdots < {a_n}$ be a finite sequence of positive integers. R. L. Graham has conjectured that $ {\max _{i,j}}\{ {a_i}/({a_i},{a_j})\} \geqslant n$. The following are proved:

(1) If $ {a_l} = p$, a prime, for some l and $ p \ne ({a_i} + {a_j})/2,1 \leqslant i < j \leqslant n$, then the conjecture holds.

(2) Given a finite sequence of positive integers $ {k_1} < {k_2} < \cdots < {k_m}$, where $ {k_I} = p$, a prime, for some I and $ {k_m} < n$, consider the set of all positive integral multiples of $ {k_1},{k_2}, \ldots ,{k_m}$ which are $ < n$. Denote these multiples by $ {a_1} < {a_2} < \cdots < {a_q}$. Define $ {P_n}$ to be a set consisting of the integers $ {a_1} < {a_2} < \cdots < {a_q} < {a_{q + 1}} < \cdots < {a_{q + r}}$ where r is maximal, such that $ n \leqslant {a_{q + 1}}$ and $ {\max _{i,j}}\{ {a_i}/({a_i},{a_j})\} < n$. Thus

$\displaystyle {P_n} = {P_n}({k_1},{k_2}, \ldots ,{k_m}).$

Then

(a) $ \vert{P_n}\vert \geqslant n$ for at most finitely many n.

(b) If $ \vert{P_n}\vert < n$ for $ n < \mathrm{l.c.m.}\{ k_1, k_2, \ldots, k_m \} $ then $ \vert{P_n}\vert < n$ for all positive integers n.


References [Enhancements On Off] (What's this?)

  • [1] R. L. Graham, Unsolved problem 5749, Amer. Math. Monthly 77 (1970), 775.
  • [P] P. Erdős, Problems and results on combinatorial number theory, A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) North-Holland, Amsterdam, 1973, pp. 117–138. MR 0360509
  • [2] J. Marica and J. Schönheim, Differences of sets and a problem of Graham, Canad. Math. Bull. 12 (1969), 635–637. MR 0249388
  • [3] Riko Winterle, A problem of R. L. Graham in combinatorial number theory, Proc. Louisiana Conf. on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1970) Louisiana State Univ., Baton Rouge, La., 1970, pp. 357–361. MR 0268152
  • [4] William Yslas Vélez, Some remarks on a number theoretic problem of Graham, Acta Arith. 32 (1977), no. 3, 233–238. MR 0429708

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 10A25

Retrieve articles in all journals with MSC: 10A25


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1977-0434941-3
Article copyright: © Copyright 1977 American Mathematical Society