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 3 of 3: Membership in the sequence depends only on x mod L

Previous step Next step

L:=\prod_{p\le a_1^2}p,\qquad x\in\{a_1,a_2,\ldots\}\iff x+L\in\{a_1,a_2,\ldots\}\quad(\forall\,x\ge a_1)

Detailed analysis

Let $P$ be the finite set of small primes $p\le a_1^2$ . By step 2, every $\preceq$ -minimal term has all its prime factors in $P$ , so its radical is a divisor of $L:=\prod_{p\in P}p$ . There are therefore only finitely many $\preceq$ -minimal terms: among terms with any fixed radical, the earliest one precedes every later term with that radical. For every $\preceq$ -minimal term $a_i$ in the entire sequence we have $\operatorname{rad}(a_i)\mid L$ , and since $a_1$ itself has all its prime factors in $P$ , any $x\ge a_1$ satisfies $\gcd(x,a_i)>1$ for all $\preceq$ -minimal $a_i<x$ if and only if it satisfies this for all $\preceq$ -minimal terms in the whole sequence (if some $\preceq$ -minimal $a_i>x$ had $\gcd(x,a_i)=1$ , then $x$ could not have appeared before $a_i$ , a contradiction). Since every such radical divides $L$ , $\gcd(x+L,a_i)>1\iff\gcd(x,a_i)>1$ . Thus $x$ occurs in the sequence if and only if $x+L$ does, proving the claimed translation-periodicity.