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
DOI: https://doi.org/10.1090/S0002-9939-1977-0434941-3
MathSciNet review: 0434941
Full-text PDF

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?)


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

American Mathematical Society