Problem 6

Let

a_1,a_2,a_3,\ldots

be an infinite sequence of positive integers greater than

1

. Suppose that for all positive integers

n

, the number

a_{n+1}

is the smallest positive integer greater than

a_n

such that

\gcd(a_{n+1},a_i)>1

for every

i=1,2,\ldots,n

. Prove that there exist positive integers

T

and

L

such that

a_{n+T}=a_n+L

for every positive integer

n

Step 1 of 3: Reduce the gcd condition to ≼-minimal terms

Previous step Next step

a_m\preceq a_n\ :\Longleftrightarrow\ m\le n\ \text{and}\ \operatorname{rad}(a_m)\mid\operatorname{rad}(a_n)

Detailed analysis

For a positive integer $x$ , let $\operatorname{rad}(x)$ denote the product of distinct prime factors of $x$ . By the greedy definition of the sequence, an integer $x\ge a_1$ appears in the sequence if and only if $\gcd(x,a_i)>1$ for every $i$ with $a_i<x$ . Define a partial order on the sequence by $a_m\preceq a_n$ when $m\le n$ and $\operatorname{rad}(a_m)\mid\operatorname{rad}(a_n)$ . Whenever $a_m\preceq a_i$ , every prime dividing $\gcd(x,a_m)$ also divides $a_i$ , so $\gcd(x,a_m)>1$ automatically implies $\gcd(x,a_i)>1$ . Thus $x\ge a_1$ appears in the sequence if and only if $\gcd(x,a_i)>1$ for all $\preceq$ -minimal terms $a_i<x$ .