Chinese Mathematical Olympiad

Proof. We prove that $C=8$ satisfies the requirement.

(1) First consider the case where $a_1$ and $a_2$ are coprime. Let $d=a_2-a_1$ be the common difference. For any prime $p$, if $p\mid d$, then $p\nmid a_1$ and hence $p$ does not divide any $a_n$. If $p\nmid d$, then any consecutive $p^2$ terms of the sequence $a_n$ form a complete set of residues modulo $p^2$, among which exactly one term is divisible by $p^2$.

Let $N=4a_2$. We prove the existence of $1\le n\le N$ such that $a_n$ has no square factors. If $1\le m\le N$ and $a_m$ has a square factor, then there exists a prime $p$ such that $p^2\mid a_m$. Thus, $p\nmid d$ and $p\le \sqrt{a_N}$. Moreover, the number of terms in $a_1,a_2,\dots ,a_N$ that are divisible by $p^2$ is at most $\lceil \frac{N}{p^2}\rceil$. Therefore, the number $M$ of terms in $a_1,a_2,\dots ,a_N$ that have square factors satisfies: $$M\le \sum _{p\le \sqrt{a_N}}\lceil \frac{N}{p^2}\rceil <\sum _{p\le \sqrt{a_N}}\left(\frac{N}{p^2}+1\right)\le N\sum _{p\le \sqrt{a_N}}\frac{1}{p^2}+\sqrt{a_N}<\frac{N}{2}+\sqrt{a_N}.$$ The last inequality is due to $$\sum _p\frac{1}{p^2}<\frac{1}{4}+\sum _{k=2}^{\infty }\frac{1}{(2k-1{)}^2}<\frac{1}{4}+\sum _{k=2}^{\infty }\frac{1}{(2k-2)2k}=\frac{1}{2}.$$ When $N=4a_2$, we have $\sqrt{a_N}<\sqrt{N{a}_2}=2a_2=\frac{N}{2}$. Thus, $M<N$. Therefore, there exist numbers in $a_1,a_2,\dots ,a_N$ that have no square factors.

(2) Assume $\gcd (a_1,a_2)=\gcd (a_1,d)=q=q_1\cdots q_l>1$, where $q_1,\cdots ,q_l$ are pairwise distinct prime factors. Note that every $a_i$ is divisible by $q$. For each prime factor $q_i$, there exists an index $t_i$ such that $v_{q_i}(a_{t_i})=1$. In fact, we can take $t_i\in 1,2$ since $a_1$ and $a_2$ cannot both be divisible by $q_i^2$. By Chinese Remainder Theorem, there exists $k\in 1,2,\cdots ,q$ such that $k\equiv t_i(\mathrm{mod}{q}_i)$ for $1\le i\le l$. Thus, for $1\le i\le l$, we have $a_k\equiv a_{t_i}(\mathrm{mod}{q}_{i}d)$, which implies $v_{q_i}(a_k)=1$.

Consider the subsequence $a_k,a_{k+q},a_{k+2q},\dots$, which has common difference $qd$ and is divisible by $q^2$. By construction, $q_i^2\nmid a_k$ for $1\le i\le l$, i.e., each term in this subsequence has no square factors that are equal to $q_1,q_2,\dots ,q_l$. Let $b_i=\frac{a_{k+(i-1)q}}{q}$, then $b_1<b_2<\dots$ is an arithmetic sequence with common difference $d$, and $b_1$ is coprime to $d$. By the conclusion of (1), there exists $i\le 4b_2$ such that $b_i$ has no square factor, and since $q$ is coprime to $b_i$, $a_{k+(i-1)q}=q{b}_i$ also has no square factor. Finally, $$k+(i-1)q\le iq\le 4b_{2}q=4a_{k+q}<4(k+q)a_2\le 8d{a}_2<8a_2^2.$$