For all positive integers $n$, the function $\gamma: \mathbb{Z}^+ \to \mathbb{Z}_{\geq 0}$ is defined as, $\gamma(1) = 0$ and for all $n > 1$, if the prime factorization of $n$ is $n = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k},$ then $\gamma(n) = \alpha_1 + \alpha_2 + \dots + \alpha_k$. We have an arithmetic sequence $X = \{x_i\}_{i=1}^{\infty}$. If for a positive integer $a > 1$, the sequence $\{ \gamma(a^{x_i} -1) \}$ is also an arithmetic sequence, show that the sequence $X$ has to be constant.
Problem
Source: 2025 Turkey TST P2
Tags: number theory, Turkey, arithmetic sequence
Turker31
18.03.2025 14:08
Little bit hard
quacksaysduck
18.03.2025 15:40
Solved with ja.
Suppose otherwise. Let $X=\{c+nd\}$ where $d>0$, now consider $X'=\{c+cnd\}$, by the problem condition the gamma sequence formed by $X'$ is also an arithmetic sequence, so we only consider $X'$. Now we divide each element of $X'$ by $c$, and we take $a:=a^c$ to see that the gamma sequence is equal. So we only need to consider the case where $X=\{1+nd\}$.
We prove that for any prime $p$, there exists an integer $m$ such that for all integers $k$ where $m|1+(k-1)d$ we have $v_p(a^{1+kd}-1)\le v_p(a-1)$. Let $e=v_p(a-1)+1$, and $ord_{p^e}(a)=m$. If $\gcd(m,d)>1$ then $a^{1+kd}\not\equiv1\pmod{p^e}$, so any $m$ works and we discard this case. Otherwise, we have $a^{1+(k-1)d}\equiv1\pmod{p^e}$ and $a^{1+kd}\not\equiv1$.
Now let $r$ be a sufficiently large integer and let $M$ be the product of all $m$'s that are coprime to $d$ for each prime $p<r$. For all $k$ such that $1+(k-1)d\equiv M$ or $k\equiv-\frac1d+1$ (which is possible since $d$ and $M$ are coprime), we have $1+(k-1)d\equiv m$, so the condition for the claim above is satisfied. Now we have the bound $\gamma(a^{1+kd}-1)\le \log_r(a^{1+kd}-1) + \gamma(a-1)\le kd\log_r(a)$, where the first term comes from primes larger than $r$ and the second from the claim above. Now set $r$ such that $d\log_r(a)$ is smaller than the common difference of $\{ \gamma(a^{1+kd} -1)\}$, we have a contradiction as $k$ increases.