Problem A. 916. (October 2025)
A. 916. Let \(\displaystyle a \geq 3\) be an integer, and define \(\displaystyle f(n) = a^n - 1\) for every positive integer \(\displaystyle n\). Denote by \(\displaystyle f^{(k)}\) the \(\displaystyle k\)-iterate of \(\displaystyle f\), that is, \(\displaystyle f^{(1)}(n) = f(n)\) and \(\displaystyle f^{(k+1)}(n)=f(f^{(k)}(n))\) for \(\displaystyle k \geq 1\).
a) Prove that for any positive integer \(\displaystyle K\) there exists a positive integer \(\displaystyle M\) such that for every integer \(\displaystyle 1 \leq k \leq K\), the number \(\displaystyle f^{(k)}(M)\) is divisible by \(\displaystyle M\) if and only if \(\displaystyle k\) is divisible by \(\displaystyle 2025\).
b) Does there exist a positive integer \(\displaystyle N\) such that for every positive integer \(\displaystyle k\), the number \(\displaystyle f^{(k)}(N)\) is divisible by \(\displaystyle N\) if and only if \(\displaystyle k\) is divisible by \(\displaystyle 2025\)?
Proposed by Boldizsár Varga, Budapest
(7 pont)
Deadline expired on November 10, 2025.
Solution. a) We will look for a number \(\displaystyle M=pq_1q_2\dots q_l\), where \(\displaystyle p\) is an arbitrary prime divisor of \(\displaystyle a-1\), and \(\displaystyle q_1,q_2,\dots,q_l\) are pairwise distinct primes. If \(\displaystyle p\) is odd, let \(\displaystyle q_1\) be a primitive prime divisor of \(\displaystyle a^{p^{2024v_p(a-1)+1}}-1\), that is, a prime dividing \(\displaystyle a^{p^{2024v_p(a-1)+1}}-1\) but not dividing \(\displaystyle a^m-1\) for any \(\displaystyle m<p^{2024v_p(a-1)+1}\); such a prime exists by Zsigmondy's theorem. If \(\displaystyle p=2\), let \(\displaystyle q_1\) be a primitive prime divisor of \(\displaystyle a^{2^{2024(v_2(a-1)+v_2(a+1)-1)+1}}-1\). Then define the primes \(\displaystyle q_2,\dots,q_l\) recursively as follows: let \(\displaystyle q_{i+1}\) be a primitive prime divisor of \(\displaystyle a^{f^{(2024)}(q_i)}-1\).
Lemma. We have \(\displaystyle q_t\mid f^{(i)}(M)\) whenever \(\displaystyle 2025\mid i\), while if \(\displaystyle 2025(t-1)<i<2025t\), then \(\displaystyle q_t\nmid f^{(i)}(M)\).
Proof. We proceed by induction on \(\displaystyle t\). For \(\displaystyle t=1\), we show that \(\displaystyle q_1\) divides \(\displaystyle f^{(k)}(M)=a^{f^{(k-1)}(M)}-1\) exactly when \(\displaystyle k=0\) or \(\displaystyle k\ge2025\). This happens exactly when the multiplicative order of \(\displaystyle a\) modulo \(\displaystyle q_1\) divides \(\displaystyle f^{(k-1)}(M)\), or when \(\displaystyle k=0\). We split into two cases.
Case 1: \(\displaystyle p\) is odd. Then \(\displaystyle q_1\) divides \(\displaystyle f^{(k)}(M)\) exactly when \(\displaystyle v_p(f^{(k-1)}(M))\ge2024v_p(a-1)+1\). However, by induction on \(\displaystyle i\) we have \(\displaystyle v_p(f^{(i)}(M))=iv_p(a-1)+1\). Indeed, this is true for \(\displaystyle i=0\), and if it holds for \(\displaystyle i\), then by LTE lemma, \(\displaystyle v_p(f^{(i+1)}(M)) =v_p(a^{f^{(i)}(M)}-1) =v_p(a-1)+v_p(f^{(i)}(M)) =(i+1)v_p(a-1)+1. \) Hence \(\displaystyle q_1\) divides \(\displaystyle f^{(k)}(M)\) exactly when \(\displaystyle k\ge2025\).
Case 2: \(\displaystyle p=2\). Again, \(\displaystyle q_1\) divides \(\displaystyle f^{(k)}(M)\) exactly when \(\displaystyle v_2(f^{(k-1)}(M))\ge2024(v_2(a-1)+v_2(a+1)-1)+1\). We prove by induction that for \(\displaystyle i\ge1\) we have \(\displaystyle v_2(f^{(i)}(M))=i(v_2(a-1)+v_2(a+1)-1)+1\). For \(\displaystyle i=1\), LTE gives \(\displaystyle v_2(a^M-1) =v_2(a-1)+v_2(M)+v_2(a+1)-1 =v_2(a-1)+v_2(a+1). \) Assume now that the formula holds for \(\displaystyle i\). Then \(\displaystyle v_2(f^{(i+1)}(M)) =v_2(a^{f^{(i)}(M)}-1) =v_2(a-1)+v_2(f^{(i)}(M)) =(i+1)v_2(a-1)+v_2(a+1), \) by the induction hypothesis. Therefore \(\displaystyle v_2(f^{(k-1)}(M))\ge2024v_2(a-1)+v_2(a+1)\) holds exactly when \(\displaystyle k\ge2025\). This completes the base case.
Now assume the statement holds for some \(\displaystyle t\), and let us prove it for \(\displaystyle t+1\). The order of \(\displaystyle a\) modulo \(\displaystyle q_{t+1}\) is exactly \(\displaystyle f^{(2024)}(q_t)\), so \(\displaystyle q_{t+1}\) divides \(\displaystyle f^{(i)}(M)\) exactly when \(\displaystyle f^{(2024)}(q_t)\mid f^{(i-1)}(M)\). The key observation is the simple fact that \(\displaystyle f(x)\mid f(y)\) if and only if \(\displaystyle x\mid y\). Indeed, modulo \(\displaystyle a^x-1\), the order of \(\displaystyle a\) is \(\displaystyle x\), hence by the standard properties of multiplicative orders, \(\displaystyle a^x-1\mid a^y-1\) if and only if \(\displaystyle x\mid y\).
Iterating this fact \(\displaystyle 2024\) times, we obtain that for \(\displaystyle i\ge2025\), the divisibility \(\displaystyle f^{(2024)}(q_t)\mid f^{(i-1)}(M)\) holds if and only if \(\displaystyle q_t\mid f^{(i-2025)}(M)\). By the induction hypothesis, if \(\displaystyle 2025\mid i\), then \(\displaystyle q_{t+1}\mid f^{(i)}(M)\) (and this is also true for \(\displaystyle i=0\)). Moreover, if \(\displaystyle 2025t<i<2025(t+1)\), then \(\displaystyle 2025(t-1)<i-2025<2025t\), so \(\displaystyle q_t\nmid f^{(i-2025)}(M)\) and therefore \(\displaystyle q_{t+1}\nmid f^{(i)}(M)\). This proves the induction step.
After proving the lemma, part (a) follows immediately. If \(\displaystyle 2025l>m\), then for every \(\displaystyle i\) divisible by \(\displaystyle 2025\), the lemma shows that \(\displaystyle f^{(i)}(M)\) is divisible by each of \(\displaystyle q_1,q_2,\dots,q_l\), and clearly also by \(\displaystyle p\), hence by \(\displaystyle M\). On the other hand, if \(\displaystyle 2025\nmid i\) and \(\displaystyle i<2025l\), then there exists \(\displaystyle t\le l\) such that \(\displaystyle 2025(t-1)<i<2025t\), and therefore \(\displaystyle q_t\nmid f^{(i)}(M)\) by the lemma. Consequently, \(\displaystyle M\nmid f^{(i)}(M)\).
b) We show that this is impossible. In fact, we prove the stronger statement that if \(\displaystyle N\mid f^{(2025k)}(M)\) for every \(\displaystyle k\ge0\), then \(\displaystyle N\mid f^{(L)}(M)\) for all sufficiently large \(\displaystyle L\).
We proceed by strong induction on \(\displaystyle N\). The case \(\displaystyle N=1\) is trivial. Assume the statement has already been established for all positive integers smaller than \(\displaystyle N\). Define \(\displaystyle g(x)=\mathrm{ord}_a(x)\) whenever \(\displaystyle (a,x)=1\).
The key observation is that for every \(\displaystyle x\), the divisibility \(\displaystyle x\mid f^{(i+2025)}(M)\) holds if and only if \(\displaystyle g^{(2025)}(x)\) is defined and \(\displaystyle g^{(2025)}(x)\mid f^{(i)}(M)\). This follows immediately by induction from the elementary fact that \(\displaystyle x\mid f^{(i)}(M)\) if and only if \(\displaystyle g(x)\mid f^{(i-1)}(M)\).
Now let \(\displaystyle N'=g^{(2025)}(N)\). Since \(\displaystyle g(x)\mid\varphi(x)<x\) by the Euler–Fermat theorem, we have \(\displaystyle N'<N\). Moreover, the previous observation implies that \(\displaystyle N'\mid f^{(2025k)}(M)\) for every \(\displaystyle k\ge0\). Applying the induction hypothesis to \(\displaystyle N'\), we conclude that \(\displaystyle N'\mid f^{(L)}(M)\) for all sufficiently large \(\displaystyle L\). Using the key observation once more, it follows that \(\displaystyle N\mid f^{(L+2025)}(M)\) for all sufficiently large \(\displaystyle L\). Thus the induction step is complete, and the proof follows.
Statistics:
12 students sent a solution. 7 points: Ali Richárd, Aravin Peter, Bodor Mátyás, Gyenes Károly (4 students). 6 points: Forrai Boldizsár, Morvai Várkony Albert, Vigh 279 Zalán (3 students). 4 points: 2 students. 3 points: 1 student. 2 points: 1 student. irregular: 1 script.
Problems in Mathematics of KöMaL, October 2025