Given is an arithmetic progression {$a_n$} of positive integers. Prove that there exist infinitely many $k$, such that $\omega (a_k)$ is even and $\omega (a_{k+1})$ is odd ($\omega (n)$ is the number of distinct prime factors of $n$). $\textit {Proposed by Viktor Simjanoski and Nikola Velov}$
Problem
Source: Macedonian TST 2022, P5
Tags: number theory
RagvaloD
21.05.2022 14:45
If $(a,b)=1$ then $\omega(ab)=\omega(a)+\omega(b)$ Let we have only finite number of such $k$ From condition follows that exist $N$ such that for $k>N$ we have that $\omega (a_k)$ have same parity. Now take some $i>N$ and let $a=a_i$ and difference in sequence is $d$ For every natural $n$ we have that $\omega(a+d*(na^2))=\omega (a (1+n*da))=\omega(a)+\omega(1+n*da) \to \omega (1+n*da)$ is even for every $n$, and so $1+n*da$ is composite But $1+n*da$ is arithmetic progression and by Dirichlet's theorem it is consists prime numbers, so we got contradiction So we have infinitely many such $k$
laikhanhhoang_3011
21.05.2022 15:51
-the problem has change-
laikhanhhoang_3011
05.02.2023 11:57
Assume $a_n=a_1+(n-1).d.$
Take the contradict, assume $N$ is the largest indicent such that $\omega (a_N)$ is even and $\omega (a_{N+1})$ is odd.
Let $p<q$ be two primes such that $p,q > max \left (a_{N+1};a_1;d \right ) \rightarrow (p,d)=(p,a_1)=(q,d)=(q,a_1)=1.$
$\bullet$ If $\omega(a_1)$ is odd, consider $a_{\frac{p^{\varphi (d)}-1}{d}}=a_1.p^{\varphi (d)}>a_{N+1} ,$
$$\omega \left(a_{\frac{p^{\varphi (d)}-1}{d}} \right)=\omega \left(a_1 \right)+\omega \left ( p^{\varphi (d)} \right )=\omega \left(a_1 \right)+1$$,which is even.
And $a_{\frac{(pq)^{\varphi (d)}-1}{d}}=a_1.(pq)^{\varphi (d)} ,$
$$\omega \left ( a_{\frac{(pq)^{\varphi (d)}-1}{d}} \right )=\omega \left ( a_1.(pq)^{\varphi (d)} \right )=\omega(a_1) + \omega \left ( (pq)^{\varphi (d)} \right )=\omega(a_1) +2$$, which is odd.
So choose the largest indicent $k \in \left [ \frac{p^{\varphi (d)}-1}{d};\frac{(pq)^{\varphi (d)}-1}{d} \right )$ such that $\omega(a_k)$ is even (definitely exists). Then $\omega (a_{k+1})$ is odd.
$\bullet$ If $\omega(a_1)$ is even, consider $a_{\frac{(pq)^{\varphi (d)}-1}{d}}$ and $a_{\frac{q^{2\varphi (d)}-1}{d}}$ similarly as above.
Q.E.D