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 2 of 3: No ≼-minimal term has a prime factor p > a1²

Previous step Next step

a_n=pc\ (p>a_1^2),\ q\mid\gcd(a_1,a_n)\ \Longrightarrow\ \exists\,k\ge0:\ q^kc\in[a_1,a_n)\ \text{and}\ \operatorname{rad}(q^kc)=\operatorname{rad}(c)\mid\operatorname{rad}(a_n)

Detailed analysis

Call a prime $p$ large if $p>a_1^2$ and small if $p\le a_1^2$ . We prove by induction on $n\ge1$ that if $a_n$ is divisible by a large prime $p$ , then $a_n$ is not $\preceq$ -minimal. Write $a_n=pc$ and choose any prime $q\mid\gcd(a_1,a_n)$ ; then $q\le a_1<a_1^2<p$ , so $q\ne p$ and therefore $q\mid c$ . In the geometric progression $c,qc,q^2c,\ldots$ of ratio $q\le a_1$ , since $a_n/a_1\ge p/a_1>a_1\ge q$ , at least one term $x:=q^kc$ lies in the interval $[a_1,a_n)$ . For every $\preceq$ -minimal term $a_i<a_n$ , the induction hypothesis says the large prime $p$ does not divide $a_i$ , so $\gcd(q^kc,a_i)\ge\gcd(c,a_i)=\gcd(pc,a_i)=\gcd(a_n,a_i)>1$ . By step 1, $x=q^kc$ must appear in the sequence as some $a_m$ with $m<n$ (since $x<a_n$ ). Because $q\mid c$ , we have $\operatorname{rad}(q^kc)=\operatorname{rad}(c)\mid\operatorname{rad}(pc)=\operatorname{rad}(a_n)$ , so $a_m\prec a_n$ and $a_n$ is not $\preceq$ -minimal.