On a conjecture of Graham concerning greatest common divisors (1977)

Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="a 1 greater-than a 2 greater-than midline-horizontal-ellipsis greater-than a Subscript n"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>a</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> <mml:mo>></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>a</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:mrow> <mml:mo>></mml:mo> <mml:mo>⋯</mml:mo> <mml:mo>></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>a</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">{a_1} > {a_2} > \cdots > {a_n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be a finite sequence of positive integers. R. L. Graham has conjectured that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="max Underscript i comma j Endscripts left-brace a Subscript i Baseline slash left-parenthesis a Subscript i Baseline comma a Subscript j Baseline right-parenthesis right-brace greater-than-or-slanted-equals n"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:munder> <mml:mo movablelimits="true" form="prefix">max</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>i</mml:mi> <mml:mo>,</mml:mo> <mml:mi>j</mml:mi> </mml:mrow> </mml:munder> </mml:mrow> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>a</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>a</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:mrow> <mml:mo>,</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>a</mml:mi> <mml:mi>j</mml:mi> </mml:msub> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> <mml:mo fence="false" stretchy="false">}</mml:mo> <mml:mo>⩾</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">{\max _{i,j}}\{ {a_i}/({a_i},{a_j})\} \geqslant n</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. The following are proved: (1) If <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="a Subscript l Baseline equals p"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>a</mml:mi> <mml:mi>l</mml:mi> </mml:msub> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>p</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">{a_l} = p</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, a prime, for some <italic>l</italic> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p not-equals left-parenthesis a Subscript i Baseline plus a Subscript j Baseline right-parenthesis slash 2 comma 1 less-than-or-slanted-equals i greater-than j less-than-or-slanted-equals n"> <mml:semantics> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>≠</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>a</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:mrow> <mml:mo>+</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>a</mml:mi> <mml:mi>j</mml:mi> </mml:msub> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo>⩽</mml:mo> <mml:mi>i</mml:mi> <mml:mo>></mml:mo> <mml:mi>j</mml:mi> <mml:mo>⩽</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">p \ne ({a_i} + {a_j})/2,1 \leqslant i > j \leqslant n</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, then the conjecture holds. (2) Given a finite sequence of positive integers <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k 1 greater-than k 2 greater-than midline-horizontal-ellipsis greater-than k Subscript m"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>k</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> <mml:mo>></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>k</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:mrow> <mml:mo>></mml:mo> <mml:mo>⋯</mml:mo> <mml:mo>></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>k</mml:mi> <mml:mi>m</mml:mi> </mml:msub> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">{k_1} > {k_2} > \cdots > {k_m}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k Subscript upper I Baseline equals p"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>k</mml:mi> <mml:mi>I</mml:mi> </mml:msub> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>p</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">{k_I} = p</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, a prime, for some <italic>I</italic> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k Subscript m Baseline greater-than n"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>k</mml:mi> <mml:mi>m</mml:mi> </mml:msub> </mml:mrow> <mml:mo>></mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">{k_m} > n</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, consider the set of all positive integral multiples of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k 1 comma k 2 comma ellipsis comma k Subscript m Baseline"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>k</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> <mml:mo>,</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>k</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:mrow> <mml:mo>,</mml:mo> <mml:mo>…</mml:mo> <mml:mo>,</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>k</mml:mi> <mml:mi>m</mml:mi> </mml:msub> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">{k_1},{k_2}, \ldots ,{k_m}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> which are <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="greater-than n"> <mml:semantics> <mml:mrow> <mml:mo>></mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">> n</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. Denote these multiples by <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="a 1 greater-than a 2 greater-than midline-horizontal-ellipsis greater-than a Subscript q"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>a</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> <mml:mo>></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>a</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:mrow> <mml:mo>></mml:mo> <mml:mo>⋯</mml:mo> <mml:mo>></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>a</mml:mi> <mml:mi>q</mml:mi> </mml:msub> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">{a_1} > {a_2} > \cdots > {a_q}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. Define <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper P Subscript n"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>P</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{P_n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> to be a set consisting of the integers <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="a 1 greater-than a 2 greater-than midline-horizontal-ellipsis greater-than a Subscript q Baseline greater-than a Subscript q plus 1 Baseline greater-than midline-horizontal-ellipsis greater-than a Subscript q plus r"> <mml:semantics>