Az A. 916. feladat (2025. október)

A. 916. Legyen \(\displaystyle a\geq3\) egész szám, és legyen \(\displaystyle f(n)=a^n-1\) minden \(\displaystyle n\) pozitív egészre. Jelölje \(\displaystyle f^{(k)}\) az \(\displaystyle f\) függvény \(\displaystyle k\)-szoros iteráltját, tehát \(\displaystyle f^{(1)}(n)=f(n)\), és \(\displaystyle f^{(k+1)}(n)=f\big(f^{(k)}(n)\big)\), ha \(\displaystyle k\geq 1\).

a) Bizonyítsuk be, hogy tetszőleges \(\displaystyle K\) pozitív egészhez létezik olyan \(\displaystyle M\) pozitív egész szám, hogy minden \(\displaystyle 1\leq k\leq K\) egész esetén \(\displaystyle f^{(k)}(M)\) pontosan akkor osztható \(\displaystyle M\)-mel, ha \(\displaystyle k\) osztható \(\displaystyle 2025\)-tel.

b) Létezik-e olyan \(\displaystyle N\) pozitív egész szám, amelyre minden \(\displaystyle k\) pozitív egész esetén \(\displaystyle f^{(k)}(N)\) pontosan akkor osztható \(\displaystyle N\)-nel, ha \(\displaystyle k\) osztható \(\displaystyle 2025\)-tel?

Javasolta: Varga Boldizsár (Budapest)

(7 pont)

A beküldési határidő 2025. november 10-én LEJÁRT.

A megoldás csak angol nyelven elérhető. Google fordítás

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.

Statisztika:

12 dolgozat érkezett.
7 pontot kapott:	Ali Richárd, Aravin Peter, Bodor Mátyás, Gyenes Károly.
6 pontot kapott:	Forrai Boldizsár, Morvai Várkony Albert, Vigh 279 Zalán.
4 pontot kapott:	2 versenyző.
3 pontot kapott:	1 versenyző.
2 pontot kapott:	1 versenyző.
Nem versenyszerű:	1 dolgozat.

A KöMaL 2025. októberi matematika feladatai