Prove that there exist $C>0$, which satisfies the following conclusion: For any infinite positive arithmetic integer sequence $a_1, a_2, a_3,\cdots$, if the greatest common divisor of $a_1$ and $a_2$ is squarefree, then there exists a positive integer $m\le C\cdot {a_2}^2$, such that $a_m$ is squarefree. Note: A positive integer $N$ is squarefree if it is not divisible by any square number greater than $1$. Proposed by Qu Zhenhua
Problem
Source: China MO 2023 P5
Tags: number theory
30.12.2022 09:35
David-Vieta wrote: Prove there exist $C>0$, which satisfies the following conclusion: For any infinite positive integer sequence $a_1, a_2, a_3,\cdots$, if the greatest common divisor of $a_1$ and $a_2$ Is squarefree, then there exists a positive integer $m\le C\cdot {a_2}^2$, such that $a_m$ is squarefree. Note: A positive integer $N$ Is squarefree if it is not divisible by any square number greater than 1. Am I misunderstanding something? Suppose such a constant exists. Take the sequence $a_n = n^2$ for $n \ge 2$ and $a_1 = 9$. Then none of $a_m$ is squarefree but $\gcd(a_1, a_2) = 1$ which is squarefree -- contradiction.
30.12.2022 09:41
$\{a_i\}$ is an arithmetic progression.
30.12.2022 10:32
Sorry,ignore
30.12.2022 10:43
$\sum_{p\text{ prime}}\dfrac1{p^2}<1$
30.12.2022 11:03
I think it's quite similar to 2020 China South-east Grade 11 P7.
30.12.2022 23:48
31.12.2022 07:32
Classify primes into three types: If a prime $p$ has $p^2 \mid a_2 - a_1$, or if $p \mid a_2 - a_1$ but not $\gcd(a_1, a_2)$, then the prime is completely harmless; no term of the sequence is divisible by $p^2$ If $p \nmid a_2 - a_1$, then we say $p$ is \alert{mostly harmless}. Otherwise, if $p \mid \gcd(a_1, a_2)$ and $\nu_p(a_2 - a_1) = 1$; we say $p$ is \alert{scary}. Let $D = \prod \left( \text{scary }p \right) \le |a_2-a_1| < a_2$. Say a term $a_i$ is good if it's not divisible by the square of any scary prime. Claim: Among any $D$ consecutive terms of $(a_n)_n$, exactly $\varphi(D)$ are good. Claim: If $p$ is a mostly harmless prime, among any $p^2 \cdot D$ consecutive terms, exactly $\varphi(D)$ good ones satisfy $p^2 \mid a_i$. Proof. By Chinese remainder theorem. $\blacksquare$ Let $N$ be large and consider only the terms $a_1$, \dots, $a_N$ henceforth. If $p$ is a mostly harmless prime with $p < \sqrt N$, the number of good terms divisible by $p^2$ is at most $\varphi(D) \left\lceil \frac{N}{p^2 D} \right\rceil$. On the other hand, if $\sqrt{N} \le p \le \sqrt{a_N}$, the number of terms divisible by $p^2$ is at most $1$, full stop. And if $p > \sqrt{a_N}$, then $p^2$ can't divide any terms. Therefore, the number of not-squarefree good terms is bounded by \begin{align*} &\phantom{<} \sum_{p < \sqrt N} \left( \varphi(D) \cdot \left\lceil \frac{N}{p^2 D} \right\rceil \right) + \sum_{\sqrt N \le p \le \sqrt{a_N}} 1 \\ &< \frac{\varphi(D)}{D} N \sum_{p} \frac{1}{p^2} + \left( \varphi(D) \cdot O \left( \frac{\sqrt{N}}{\log N} \right) + O\left( \frac{\sqrt{ND}}{\log(ND)} \right) \right) \\ &< \frac{\varphi(D)}{2D} N + \varphi(D) \cdot O \left( \frac{\sqrt{N}}{\log N} \right) \end{align*}where we have used three well-known facts: $\sum_{p\text{ prime}} p^{-2} < \frac{1}{2}$, the prime number theorem, and the inequality $0.01 \sqrt D \le \varphi(D)$ which is valid for any $D \ge 1$ (and is proved by multiplicativity of $\varphi(x)/x$, and checking at prime powers). On the other hand, the number of good terms was at least \[ \varphi(D) \cdot \left\lfloor \frac{N}{D} \right\rfloor > \frac{\varphi(D)}{D} N - \varphi(D) \]So we will have a squarefree term as long as \[ \frac{\varphi(D)}{2D} N > \varphi(D) \cdot O \left( \frac{\sqrt{N}}{\log N} \right) \]which is certainly true if $N > O(\sqrt{D})$. As $D < a_2$, we're done.
06.01.2023 06:35
I can provide a interesting solution ,using two estimation method .The only regret is that it is a little complex.
21.04.2023 12:05
Several similar problems after this old Tuymaada problem: https://artofproblemsolving.com/community/c6h102434p576239
30.07.2023 08:48
Friends of Chinese, please translate this solution . https://m.toutiao.com/article/7183169007346926091/?source=seo_tt_juhe&upstream_biz=toutiao_pc
21.08.2023 19:38
Let $d = \gcd(a_1, a_2)$. Now, consider $a_1, a_2, \dots, a_N$. Note that at least $\frac{\phi(d)}{d} \cdot N$ numbers in the sequence is not divisible by factors in $D$. Furthermore, note that $a_N < Na_2$. As such, the number of non-squarefree numbers in $a_1, a_2, \dots, a_N$ is thus at most \begin{align*} &\sum_{p < \sqrt{Na_2}, p \not\in D} \left\lceil \frac{\frac{\phi(d)}{d} \cdot N}{p^2} \right\rceil < \sum_{p < \sqrt{Na_2}, p \not\in D} \frac{\frac{\phi(d)}{d} \cdot N}{p^2} + (\phi(d) + o(1)) \cdot \frac{2\sqrt{Na_2}}{\ln(Na_2)} \\ &< \frac{\phi(d)}{2d} \cdot N + (\phi(d) + o(1)) \cdot \frac{2\sqrt{Na_2}}{\ln(Na_2)}. \end{align*}If we take $N = Ca_2^2$, it remains to show that \[ \frac{\phi(d)}{2d} \cdot Ca_2^2 + (\phi(d) + o(1)) \cdot \frac{2\sqrt{C}a_2^{\frac32}}{3\ln(Ca_2)} < Ca_2^2 \\ \]which follows by taking large $C$ and $\phi(d) < d$.
15.11.2024 17:41
See that because of Prime Number Theorem on APs, we get that there is a squarefree term in the sequence eventually and hence assume that $a_2 \geq 10^{100}$. Now say that $a_1=a$, $a_2-a_1=d$ and $\gcd(a,d)=g$. Also throughout the proof, let $p$ denote a general prime. $\bullet$ If $p \nmid d$, then the density of natural numbers $n$ such that $p^2 \mid a+nd$ is $\frac 1{p^2}$. $\bullet$ If $p \mid a$ and $\nu_p(d)=1$, then the density of natural numbers $n$ such that $p^2 \mid a+nd$ is $\frac 1p$. $\bullet$ For any other $p$, there are no $n$ such that $p^2 \mid a+nd$. Now since $g$ is squarefree, due to CRT shenanigans we see that the maximum number of non squarefree numbers among $a_1$, $\dots$, $a_m$ is \begin{align*} \left \lceil m \left(1-\frac{\varphi(g)}g \right) \right \rceil + \sum_{p \leq \sqrt{a_m}} \left \lceil \frac{\frac{\varphi(g)}g \cdot m}{p^2} \right \rceil & \leq m - \frac{\varphi(g)}g \cdot \frac m2+\frac{2.2 \sqrt{a_m}}{\log a_m} \\ & < m - \frac{\varphi(g)}g \cdot \frac m2+\frac{2.2 \sqrt{ma_2}}{\log ma_2} \end{align*}Say $m=100a_2^2$. So we want to prove that \[\frac{\varphi(g)}g \cdot 50 \sqrt{a_2} \geq \frac{22}{3 \log \left(100^{\frac 13} \cdot a_2 \right)} \text{ or } 50 \varphi(a_2) \geq \frac{22 \sqrt{a_2}}{3 \log \left(100^{\frac 13} \cdot a_2 \right)}\]due to the fact that $\frac{\varphi(g)}g \geq \frac{\varphi(a_2)}{a_2}$ as $g \mid a_2$. Now since $\varphi(a_2) \geq \sqrt{a_2}$ for $a_2 \geq 10^{100}$ (easily can be checked by multiplicity of $\varphi$ and $\sqrt{\text{ }}$); we just need to prove that \[150 \log \left(100^{\frac 13} \cdot 10^{100} \right) \geq 22\]which is very true.
08.12.2024 19:19
The bound $\mathcal O(a_2^2)$ can be improved to $\mathcal O(a_2(\ln\ln a_2)^2).$
12.01.2025 22:39
Quite similar to other solutions, mostly for storage (but I also did my best to include more details). Let $r=a_2-a_1$ and $d=\gcd(a_1, a_2)=\gcd(a_1, r).$ Then $a_n=a_1+(n-1)r=d\left[\frac{a_1}{d}+(n-1)\frac rd\right].$ Let $p$ be a prime number. The hardest ones to bound are those such that $p|d$ but not $\frac rd$. Let $S$ be the set of all these primes and let \[P=\prod_{p\in S}p.\]Also note that we don't have to worry at all for the primes which divide both $d$ and $\frac rd$. For a positive integer $N$, let $A$ be the subset of $\{a_1, a_2, ..., a_N\}$ whose elements are not divisible by the square of any prime from $S$. Among any $P$ consecutive terms there are exactly $\varphi(P)$ terms with this property. This implies \[|A| \ge \varphi(P)\left \lfloor \frac{N}{P} \right \rfloor>\frac{\varphi(P)}{P}N-\varphi(P).\]Let $B$ be the set of all primes that divide $d$. For a prime $p$ not in $B$, by CRT, for any $p^2\cdot P$ consecutive terms exactly $\varphi(P)$ are divisible by $p^2$, but are not divisible by the square of any prime in $S$. All primes whose square divides some term of the sequence are either in $S$ or in $B$. Let $q\in B$. If $q^2|a_n$ for some positive integer $n$, then \[q^2|d\left[\frac{a_1}{d}+(n-1)\frac rd\right]\implies q^2|\frac{a_1}{d}+(n-1)\frac rd\implies q<\sqrt{\frac{na_2}{d}}.\]Also, if $p\ge\sqrt{N}$ is a prime which belongs to $B$ and $p^2$ divides both $a_i$ and $a_j$, then \[p^2|r(i-j)\]and this is clearly impossible if $i-j<N$. Thus $p^2$ divides at most one element of $A$. Now we'll bound the number of elements of $A$ which are not squarefree. Let $T$ denote this number. Then \[T \le \sum_{p \in B, p<\sqrt{N}}\varphi(P)\left \lceil \frac{N}{p^2\cdot P} \right \rceil+\sum_{\sqrt N \le p \in B \le \sqrt{\frac{Na_2}{P}}}1\]\[T\le \frac{\varphi(P)}{P}N\sum_{p \in B}\frac{1}{p^2}+\varphi(P)O\left(\frac{\sqrt N}{\log \sqrt N}\right)+\left(\frac{\sqrt{\frac{Na_2}{P}}}{\log{\frac{Na_2}{P}}}\right)\]\[T<\frac{\varphi(P)}{2P}N+\varphi(P)O\left(\frac{\sqrt N}{\log \sqrt N}\right)+\sqrt{\frac{a_2}{P}}O\left(\frac{\sqrt N}{\log \sqrt N}\right).\]We want this to still be under the lower bound for $|A|$, i.e. \[\frac{\varphi(P)}{P}N>\varphi(P)+\varphi(P)O\left(\frac{\sqrt N}{\log \sqrt N}\right)+\sqrt{\frac{a_2}{P}}O\left(\frac{\sqrt N}{\log \sqrt N}\right)\]Dividing by $\sqrt{N}$ and absorbing $\varphi(P)$ in $\varphi(P)O\left(\frac{\sqrt N}{\log \sqrt N}\right)$: \[\sqrt N>P\cdot O\left(\frac{1}{\log \sqrt N}\right)+\sqrt{\frac{a_2P}{\varphi(P)}}O\left(\frac{1}{\log \sqrt N}\right)\]As $P\le d<a_2$ and rewriting $N$ as $(Ca_2)^2$ it is enough to find a constant $C$ such that \[Ca_2\ge a_2\cdot O\left(\frac{1}{\log Ca_2}\right)+a_2\cdot O\left(\frac{1}{\log Ca_2}\right)\]which of course holds for a sufficiently large $C$ regardless of $a_2$. However, this is only marginally better than $O(a_2^2)$ and I would be interested in seeing the proof for $O(a_2(\log \log a_2)^2)$.