For each positive integer $k$, define $a_k$ as the number obtained from adding $k$ zeroes and a $1$ to the right of $2024$, all written in base $10$. Determine wether there's a $k$ such that $a_k$ has at least $2024^{2024}$ distinct prime divisors.
Problem
Source: PErA 2024/6
Tags: number theory
04.03.2024 17:12
The answer is yes. I am gonna assume that $a_k = 2024\underbrace{00...00}_{k}1 = 2024 \cdot 10^{k+1} + 1$. We use an induction on $N$ that there exists $k$ for which $a_{k}$ has at least $N$ distinct prime divisors. The base case is trivial. For the induction step assume that we found some $k$ such that $a_{k}$ has at least $N$ distinct prime divisors and we will prove that there exists $k'$ for which $a_{k'}$ has at least $N+1$ prime divisors. Let the primes $p_{1} < p_{2} < \cdots < p_{N}$ be the divisors of $ a_{k} = 2024 \cdot 10^{k+1} + 1$. Define a sequence $b_{m} = 2024 \cdot 10^{m \varphi({2024\cdot 10^{k+1} + 1}) + k + 1}$ for $m=1, 2, 3, \cdots$. Clearly, there are only finitely many primes dividing at least one of the terms of the sequence $(b_{m})_{m \ge 1}^{\infty}$, therefore, using Kobayashi's theorem, there are infinitely many primes dividing at least one of the terms of the sequence $c_{m} = b_{m} +1$, for $m = 1, 2, 3, \cdots$. Choose a prime $q > p_{N}$ such that $q \mid c_{t}$ for some $t \in \mathbb{N}$. Now, notice that $c_{t} = 2024 \cdot (10^{t})^{\varphi(2024 \cdot 10^{k+1} + 1)} \cdot 10^{k+1} + 1 \equiv 2024 \cdot 10^{k+1} + 1 \equiv 0 \pmod{2024 \cdot 10^{k+1} + 1}$ using that $\gcd(10^t, 2024 \cdot 10^{k+1} + 1) = 1$. What it means is that $c_{t}$ is divisible by $p_{1}, p_{2}, \cdots, p_{N}$ and also $q$, therefore if we choose $k' = t \varphi({2024\cdot 10^{k+1} + 1}) + k$, $a_{k'}$ will have at least $N+1$ distinct prime divisors and we are done. $ \ \square$