The following generalization is true: Let $P$ be a polynomial with integer coefficients such that $P(0)=0$. We denote the $k$-fold application of $P$ by $P^k$. Let $a$, $n$ and $m$ be positive integers such that: 1. $P^n(a)-a$ is divisible by $n$, 2. $\sum\limits_{k=1}^{n} k^mP^k(a)$ is not divisible by $n$. Then $n$ has a prime factor not exceeding $m+1$. The original problem is recovered by $P(x)=x^2$ and $m=2024$. Also this generalization is false if we don't assume $P(0)=0$. For instance, for $P(x)=x+1$, we can take $m=p-2$ and $a=n=p$ where $p$ is any prime.

Supercali wrote: The following generalization is true: Let $P$ be a polynomial with integer coefficients such that $P(0)=0$. We denote the $k$-fold application of $P$ by $P^k$. Let $a$, $n$ and $m$ be positive integers such that: 1. $P^n(a)-a$ is divisible by $n$, 2. $\sum\limits_{k=1}^{n} k^mP^k(a)$ is not divisible by $n$. Then $n$ has a prime factor not exceeding $m+1$. The original problem is recovered by $P(x)=x^2$ and $m=2024$.

math_comb01 wrote:

The proof of the lemma is incomplete, why is $d<n$? Also the last step seems wrong, you can't just replace $a$ by $a^t$ here.

Standard, but I couldn't solve it in test because the antibiotics threw me off ... missed my chance to solve the best NT in TST I will solve the generalization, I think the generalization is not far from the ideas I had. Before moving on to the solution, I would like to remark the very obvious and trivial fact not worth stating in the main body of the solution that $n$ is odd, otherwise we are done. Assume FTSOC that the problem statement is false. I begin with a claim: Claim. Let $a,n$ be positive integers so that the chain $a\rightarrow P(a)\rightarrow \cdots$ forms a cycle modulo $n$. If $d$ is the length of the least cycle, then we have $d<n$. Proof. Assume not, let $d\ge n$. Consider the valuation at $a$ of the polynomials $P^0, P^1,\cdots, P^{d-1}$. If they do not form a complete residue system mod $n$, then there exist $0\leq i<j\le d-1$ so that the valuation at $a$ of $P^i$ and $P^j$ modulo $n$ coincide. This implies that \[P^{d-i}(P^i(a))\equiv P^{d-i}(P^j(a)) \pmod{n}\]or equivalently that $P^{j-i}(a)\equiv a\pmod{n}$, but this is a contradiction, as $j-i< d$. So, these numbers form a complete residue system modulo $n$. This forces $d=n$ for obvious reasons. Choose $i$ so that the valuation at $a$ of $P^{i}$ is zero modulo $n$, then, from the condition that $P(0)=0$, we see that $P^i(a) \mid P^{i+1}(a)$ and so the valuation at $a$ of $P^{i+1}$ is zero, impossible. Thus, both cases lead to a contradiction and therefore indeed we have $d\le n$. Back to our problem, define \[f(t) = \sum_{k=1}^tk^mP^{k}(a)\]and $d_t$ to be the length of the smallest cycle in the chain $a\rightarrow P(a)\cdots$ modulo $t$. Let $p$ be any prime divisor of $n$. I will prove by induction on $i$ that $p^{i}\mid f\left(\frac{n}{p^{\nu_{p}(n)-i}}\right)$ for all $0\le i\le \nu_{p}(n)$ with the base-case being straightforward. Assume this is true for $i$, then, for $i+1$, note that $d_{p^{i+1}}$ is a proper divisor of $\frac{n}{p^{\nu_p(n)-i}}$, because firstly it divides $n$, due to the first condition, and secondly, the $\nu_p$ of it cannot exceed $i$, as otherwise it will exceed $p^{i+1}$, contradicting my claim above. Therefore, we have that $$p^{i+1}\mid P^{\frac{n}{p^{\nu_p(n)-i}}}(a)-a$$ Now, the idea is to re-write $f\left(\frac{n}{p^{\nu_p(n)-i-1}}\right)$ in a very tractable manner. One thing which we can certainly take advantage of is, the divisibility relation presented above. Let us see how: \begin{align*} f\left(\frac{n}{p^{\nu_p(n)-i-1}}\right) &= \sum_{i=1}^{\frac{n}{p^{\nu_p(n)-i-1}}}i^mP^{i}(a) \\ &\equiv \sum_{i=1}^{\frac{n}{p^{\nu_p(n)-i}}}\sum_{j=0}^{p-1}\left(i+j\cdot\frac{n}{p^{\nu_p(n)-i}}\right)^mP^{i}(a)\pmod{p^{i+1}} \\ &\equiv \sum_{i=1}^{\frac{n}{p^{\nu_p(n)-i}}}P^i(a) \sum_{j=0}^{p-1}i^m + m\cdot\frac{n}{p^{\nu_p(n)-i}}\cdot j\pmod{p^{i+1}} \\ &\equiv \sum_{i=1}^{\frac{n}{p^{\nu_p(n)-i}}}p\cdot P^i(a)i^m+m\left(\frac{n}{p^{\nu_p(n)-i}}\cdot\frac{p(p-1)}{2}\right)\pmod{p^{i+1}} \\ &\equiv p\sum_{i=1}^{\frac{n}{p^{\nu_p(n)-i}}}P^i(a)i^m\pmod{p^{i+1}} \\ &\equiv pf\left(\frac{n}{p^{\nu_p(n)-i}}\right)\pmod{p^{i+1}} \\ &\equiv 0\pmod{p^{i+1}} \end{align*}Note that above we used the fact that $p$ is odd. This proves my claim that $p^i\mid f\left(\frac{n}{p^{\nu_p(n)-i}}\right)$ for all $0\le i\le\nu_p(n)$, and therefore we have proven that $p^{\nu_p(n)}\mid n$ for all primes $p$ dividing $n$, meaning that $n\mid f(n)$, a contradiction to the second condition. Therefore we are done.

EDIT: OMG It's my 800th post and this is problem 8! @below right.. but the fix is not too hard, like the terms inside form a complete residue system mod $p$, and we want to prove that $p\mid 1^m+\cdots+(p-1)^m$ which is obvious when $p\ge m+2$. Also I think there is a confusion as I used the same index $i$ twice.... will fix later

rama1728 wrote: \begin{align*} f\left(\frac{n}{p^{\nu_p(n)-i-1}}\right) &= \sum_{i=1}^{\frac{n}{p^{\nu_p(n)-i-1}}}i^mP^{i}(a) \\ &\equiv \sum_{i=1}^{\frac{n}{p^{\nu_p(n)-i}}}\sum_{j=0}^{p-1}\left(i+j\cdot\frac{n}{p^{\nu_p(n)-i}}\right)^mP^{i}(a)\pmod{p^{i+1}} \\ &\equiv \sum_{i=1}^{\frac{n}{p^{\nu_p(n)-i}}}P^i(a) \sum_{j=0}^{p-1}i^m + m\cdot\frac{n}{p^{\nu_p(n)-i}}\cdot j\pmod{p^{i+1}} \\ &\equiv \sum_{i=1}^{\frac{n}{p^{\nu_p(n)-i}}}p\cdot P^i(a)i^m+m\left(\frac{n}{p^{\nu_p(n)-i}}\cdot\frac{p(p-1)}{2}\right)\pmod{p^{i+1}} \\ &\equiv p\sum_{i=1}^{\frac{n}{p^{\nu_p(n)-i}}}P^i(a)i^m\pmod{p^{i+1}} \\ &\equiv pf\left(\frac{n}{p^{\nu_p(n)-i}}\right)\pmod{p^{i+1}} \\ &\equiv 0\pmod{p^{i+1}} \end{align*} @above this calculation fails for the case $i=0$ (i.e., for the first step in the induction step). In fact this is where you have to use $p \geq m+2$. Here is my original solution (Solution A) adapted for the generalization: Let $n$ be a positive integer. Call a positive integer $a$ good for $n$ if $n \mid P^n(a)-a$. Define $d_n(a)=d$ to be the smallest positive integer such that $n \mid P^d(a)-a$. Then $P^{d+k}(a) \equiv P^k(a) \pmod n$ holds for $k \geq 0$ $\implies$ $P^i(a) \pmod n$ is periodic with period $d$. The minimality of $d$ implies that it is in fact the smallest period. Therefore $d \mid n$. So $d \mid n \mid P^d(a)-a$ $\implies$ $a$ is good for $d$ as well. Assume $n>1$. If the sequence contains the residue $0$ modulo $n$, then since $P(0)=0$ and the sequence is periodic, all terms are $0$ modulo $n$. Else the sequence doesn't contain the residue $0$. In any case the sequence cannot contain all residues modulo $n$, so $d_n(a) < n$. Lemma. If $a$ is good for $n$, then for any non-negative integer $t$, the numbers $P^i(a)^t+i$ for $i=1, \dots n$ form a complete residue system modulo $n$. Proof: We will prove this by induction on $n$. Base case $n=1$ is true since there's only one number. Consider $n>1$ for the induction step. Assume for the sake of contradiction that there exist distinct $i,j \leq n$ such that $P^i(a)^t+i \equiv P^j(a)^t+j \pmod n$. Let $d=d_n(a)$. Then $d \mid n$, $d<n$ and $a$ is good for $d$ as well. So $P^i(a)^t+i \equiv P^j(a)^t+j \pmod d$. Note that, since $a$ is good for $d$, reducing $i,j$ modulo $d$ does not change the values of $P^i(a)^t+i \pmod d$ and $P^j(a)^t+j \pmod d$. Therefore, by induction hypothesis, $i \equiv j \pmod d$. But then $P^i(a)^t \equiv P^j(a)^t \pmod n$ $\implies$ $i \equiv j \pmod n$. Contradiction! Hence the numbers are pairwise distinct modulo $n$, and so form a complete residue system. $\blacksquare$ We return to the main problem. Clearly we must have $n>1$. Assume for the sake of contradiction that all the prime factors of $n$ are $ \geq m+2$. We will prove using induction on $i$ that $$\sum_{k=1}^n k^iP^k(a)^t$$is divisible by $n$ for any good $a$, any non-negative integer $t$, and all $0 \leq i \leq m$, which will give us the desired contradiction. For the base case, $i=0$. By Lemma A1, $$\sum_{k=1}^n (P^k(a)^t+k)\equiv \sum_{k=1}^n k \pmod n\implies \ \sum_{k=1}^n P^k(a)^t \equiv 0 \pmod n.$$Assume that the hypothesis holds for all $i < l$ for some $l \leq m$. Then by the Lemma, $$\sum_{k=1}^n (P^k(a)^t+k)^{l+1}\equiv \sum_{k=1}^n k^{l+1} \pmod n\implies \sum_{i=0}^l \binom{l+1}{i} \sum_{k=1}^n k^i P^k(a)^{t(l+1-i)} \equiv 0 \pmod n.$$By induction hypothesis, all the sums of the form $$\sum_{k=1}^n k^i P^k(a)^{t(l+1-i)}$$for $0 \leq i \leq l-1$ are divisible by $n$. Hence we get $$n \mid (l+1) \sum_{k=1}^n k^l P^k(a)^t.$$But all prime factors of $n$ are at least $m+2 \geq l+2$, which implies $\gcd(n,l+1)=1$. Therefore $$n \mid \sum_{k=1}^n k^l P^k(a)^t,$$which completes the induction.

Solved with brainfertilzer Suppose otherwise. It's well known that for any nonnegative integer $i$, $1^i + 2^i + \cdots + p^i$ is $0\pmod p$ iff $p-1 \nmid i$, so for all primes $p > 2024$, $1^i + 2^i + \cdots + p^i \equiv 0\pmod p\forall i \le 2024$ since $2025$ isn't a prime. Claim: $n$ has a prime factor not dividing $a$ Proof: Suppose otherwise. Then for any prime factor dividing $n$, we have $\nu_p(a^{2^n} - a ) = \nu_p(a)$, so $\nu_p(n) \le \nu_p(a)$, meaning that $n \mid a$. Now, the second condition will be false. $\square$ Let $p$ be an arbitrary prime divisor of $n$ and $f(k) = a^{2^k}$. Also let $d$ be the smallest nonnegative integer such that $a^{2^d} - a$ is a multiple of $n$. Clearly $d < n$ and $d\mid n$. Let $g(x) = x^2$. Notice that $f(x) = g^x(a)$. Additionally, $g^x(a_1) \equiv g^x(a_2) \pmod r$ if $a_1 \equiv a_2 \pmod r$ for any positive integer $r$. Claim: If $f(x) \equiv a\pmod r$, then $f(mx) \equiv a\pmod r$ for any positive integers $m$ and $r$. Also if $f(x) \equiv f(y) \equiv a\pmod r$ for $x < y$, then $f(y - x ) \equiv f(x + y) \equiv a\pmod r$. Proof: To show $f(mx) \equiv a\pmod r$ when $f(x) \equiv a\pmod r$, we induct on $m$. This is clearly true for $m = 1$. If it's true for $m - 1$, then we have\[f(mx) = g^{mx} (a) = g^x(g^{(m-1) x} (a) ) \equiv g^x(a) \equiv a\pmod r \]Now if $f(x) \equiv f(y) \equiv a\pmod r$, then we have\[a \equiv f(y) \equiv g^y(a) \equiv g^{y - x} (g^x (a)) \equiv g^{y - x} (a) \equiv f(y-x) \pmod r \]and\[ a \equiv g^y(a) \equiv g^y(g^x(a)) \equiv g^{y + x} (a)\equiv f(x+y) \pmod r \ \ \ \ \square\] Claim: For any divisor $d > 1$ dividing $n$ that has a prime factor not dividing $a$, the smallest positive integer $k$ where $f(k) \equiv a\pmod d$ is less than $d$ and divides $n$. Proof: Suppose otherwise. Choose $k$ to be the smallest number where $f(k) \equiv a\pmod d$ (must exist since it is true for $n$). First we show that $k < d$. Suppose otherwise. Then none of $f(1), f(2), \ldots, f(d - 1)$ are $a\pmod d$. Additionally, none of these numbers are $0\pmod d$ as $d$ cannot divide a power of $a$. Therefore $\{f(1), f(2), \ldots, f(d-1)\}$ occupy at most $d - 2$ residues modulo $d$, so two of them are the same modulo $d$. Suppose $f(i) \equiv f(j) \pmod d$ for some $i < j$. Notice that since $f(x+N) = f(x)^{2^N} $, we have that $f(i + N) \equiv f(j + N) \pmod d$ for any positive integer $N$, so $f(x) \equiv f(x - (j - i) ) \pmod d$ for any positive integer $x > j$. Now we claim that $f(x) \not \equiv a\pmod d$ for any positive integer $x$. This is done by induction on $x$, where the base cases $1, 2, \ldots, t - 1$ are obvious. Suppose $x > t - 1$ and the result was true for everything less than $x$. We have that $f(x) \equiv f(x - (j - i)) \pmod d$, and we know that $f(x - (j - i) ) \not \equiv a\pmod d$ by the inductive hypothesis, so $f(x) \not \equiv a\pmod d$, which completes the induction. However, this is absurd since $f(n) \equiv a\pmod n$, so $f(n) \equiv a\pmod d$. Thus, $k < d$. Now we prove that $k$ divides $n$. There exist positive integers $b_1,b_2$ where $b_1k - b_2n = \gcd(n,k)$. We have $f(b_1 k) \equiv a\pmod t$ and $f(b_2 n) \equiv a\pmod d$, so $f(b_1 k - b_2 n) = f(\gcd(n,k)) \equiv a\pmod d$ also. If $k$ didn't divide $n$, then $\gcd(n,k) < k$, contradiction to the minimality of $k$. $\square$ Let $c = \frac{n}{\nu_p(n)}$. Claim: If $p^t$ is a divisor of $n$ for some positive integer $t$ and $p^{t-1} $ divides $\sum_{k=1}^{c \cdot p^{t-1} } k^{2024} f(k)$, then $p^t$ divides $\sum_{k=1}^{c \cdot p^t } k^{2024} f(k)$. Proof: If $p\mid a$, then $\nu_p(n) \le \nu_p(a^{2^n} - a) = \nu_p(a)$. This also implies $ p^t \mid a$, so $p^t$ has to divide the sum. Henceforth assume $p\nmid a$. Note that if we choose $k < p^t $ where $f(k) \equiv a\pmod{p^t}$, then since $\nu_p(k) < t$ and $k \mid n$, $k$ must divide $c p^{t-1}$, so $f(c p^{t-1}) \equiv a\pmod{p^t}$. Now we split into cases depending whether or not $t = 1$. Case 1: $t > 1$ First we prove that $(m \cdot c \cdot p^{t-1} + j)^{2024} \equiv 2024 m \cdot c \cdot j^{2023} p^{t-1} + j^{2024} \pmod{p^t}$. We have\[ (m \cdot c \cdot p^{t-1} + j)^{2024} = \sum_{i=0}^{2024} (mc)^i p^{i(t-1) } j^{2024 - i} \cdot \binom{2024}{i} \]This is clearly $0\pmod{p^t}$ for $i > 1$, since if $i > 1$, then $i(t-1) \ge 2(t-1) \ge t$ for $ t > 1$. Hence the sum only need be taken from $i = 0$ and $i = 1$, which gives us the desired result. We have\begin{align*} \sum_{k=1}^{c \cdot p^t } k^{2024} a^{2^k} \equiv \sum_{j=1}^{c \cdot p^{t-1} } \sum_{m=0}^{p - 1} (m\cdot c \cdot p^{t-1} + j)^{2024} f(j) \\ \equiv \sum_{j=1}^{c\cdot p^{t-1}} \sum_{m=0}^{p - 1 } ( 2024 m \cdot c \cdot j^{2023} \cdot p^{t-1} + j^{2024}) f(j) \equiv \sum_{j=1}^{c\cdot p^{t-1}} f(j) \sum_{m=0}^{p - 1 } ( 2024 m \cdot c \cdot j^{2023} p^{t-1} + j^{2024}) \\ \equiv \sum_{j=1}^{c\cdot p^{t-1}} f(j) \left( j^{2024} \cdot p + 2024 c \cdot j^{2023} p^{t-1} \left( 1 + 2 + \cdots + \left(p - 1 \right) \right) \right) \equiv \sum_{j=1}^{c \cdot p^{t - 1} } f(j) (j^{2024} \cdot p) \pmod{p^t} \\ \end{align*}Now note that $p^{t-1}$ divides $\sum_{j=1}^{c \cdot p^{t-1}} f(j) j^{2024}$, so $p^t $ must divide $\sum_{j=1}^{c \cdot p^{t-1} } f(j) (j^{2024} \cdot p)$, as desired. Case 2: $t = 1$ Now we have $f(c) \equiv a\pmod p$. Now using the fact that\[1^i + 2^i + \cdots + (p-1)^i \equiv 0\pmod p \forall 0 \le i \le 2024\](which follows since $p > 2024$), we find that\begin{align*} \sum_{k=1}^{cp} k^{2024} a^{2^k} \equiv \sum_{j=1}^{c} \sum_{m=0}^{p - 1} (m c + j)^{2024} f(j) \\ \equiv \sum_{j=1}^{c} f(j) \sum_{m=0}^{p - 1} (m c + j)^{2024} \equiv \sum_{j=1}^{c} f(j) \sum_{m=0}^{p-1} \sum_{i=0}^{2024} m^i c^i j^{2024 - i} \binom{2024}{i} \\ \equiv \sum_{j=1}^c f(j) \sum_{i=0}^{2024} \sum_{m=0}^{p- 1} m^i c ^i j^{2024 - i} \binom{2024}{i} \\ = \sum_{j=1}^c f(j) \sum_{i=0}^{2024} j^{2024 - i} \binom{2024}{i} \sum_{m=0}^{p - 1} m^i \\ \equiv 0 \pmod p, \end{align*}as desired. $\square$ Claim: For any nonnegative integer $t \le \nu_p(n)$, we have $p^t $ divides $\sum_{k=1}^{c \cdot p^t} k^{2024} f(k)$. Proof: This is done by induction. The base case $t = 0$ is obvious. If for any $t > 0$, the result was true for $t - 1$, then it is also true for $t$ by the above claim, so the induction is complete. $\square$ Now choosing $t = \nu_p(n)$, we get that $p^{\nu_p(n)}$ divides $\sum_{k=1}^n k^{2024} f(k)$. This is true for all primes $p$ dividing $n$, so combining gives that $n $ divides $\sum_{k=1}^n k^{2024} f(k)$, absurd. Therefore, $n$ must have a prime factor smaller than $2024$.

Suppose we have a positive integer $n$ with all prime factors greater or equal to $2027$, then call funny any number $a$ that satisfies condition 1 on the problem statement. We will now spam propeties of it and some well-known lemmas to contradict statement 2. Claim 1: If $a$ is funny so is $a^{\kappa}$ Proof: Simply note that $n \mid a^{2^n}-a \mid a^{2^n \cdot \kappa}-a^{\kappa}$ Claim 2: Denote $O_{2,a}(n)=d$ the minimal positive integer such that $n \mid a^{2^d}-a$, then $d \mid n$. Proof: Note that the sequence $b_i=a^{2^{i}}$ has period $d$ in $\pmod n$ and since $d$ is the smallest possible positive value for which we get all of the $b_i$'s are congruent to $b_0=a$ in $\pmod n$ we must have that $d \mid n$ as desired. Now this implies that if $n$ is funny so is $O_{2,a}(n)=d$ and we can make a smaller funny number always, because notice that $\pmod n$ the sequence $b_i$, by doing small casework on $\gcd(a,n)$ we can see that it will always miss at least one residue $\pmod n$ which forces $d<n$, we use this to go backwards and do something cool. Claim 3: The sequence $c_i=a^{2^i}+i$ for $a$ being a funny number (w.r.t. $n$), $i$ spanning from $0$ to $n-1$, it then covers all residues $\pmod n$. Proof: We prove this by strong induction on $n$, with the base case $n=1$ being trivial, now suppose it's true for all $n \le k-1$, we prove it for $n=k$, so if we had $a^{2^i}+i \equiv a^{2^j}+j \pmod k$, let $O_{2,a}(k)=l$ then $l \mid k$ but also $a$ is a funny number w.r.t. $l$ so from inductive hypothesis we get that $i \equiv j \pmod l$ which means $a^{2^i} \equiv a^{2^j} \pmod k$ therefore $i \equiv j \pmod k$ which is a contradiction, thus the inductive step is completed. We now prove the stronger statement that for all $0 \le \ell \le 2024$ it's true that $\sum_{k=1}^{n} k^{\ell} a^{2^k} \equiv 0 \pmod n$ (where $a$ is some funny number w.r.t $n$) by strong induction on $\ell$, we start with $\ell=0$. \[ \sum_{k=1}^{n} a^{2^k}+k \equiv \sum_{k=1}^{n} k \pmod n \; \implies \; \sum_{k=1}^{n} a^{2^k} \equiv 0 \pmod n \]Now for the inductive indcutive hypothesis assume the statement is true for all $\ell \le l-1<2024$ then we prove it for $\ell=l$. \[ \sum_{k=1}^{n} (a^{2^k}+k)^{l+1} \equiv \sum_{k=1}^{n} k^{l+1} \pmod n \; \implies \; \sum_{j=0}^{l} \binom{l+1}{j} \sum_{k=1}^{n} k^j a^{(l+1-j)2^k}= \sum_{k=1}^{n} \sum_{j=0}^{l} \binom{l+1}{j} k^{j}a^{(l+1-j) \cdot 2^k} \equiv 0 \pmod n \]Now here we use inductive hypothesis along with Claim 1 to get that: $(l+1) \cdot \sum_{k=1}^{n} k^l a^{2^k} \equiv 0 \pmod n$ and now since $l+1<2026$ we have that all of it's prime factors must be less than $2027$ therefore $\gcd(l+1,n)=1$ which gives the desired inductive hypothesis proof. Therefore we are done as $2025=45^2$ and $2024$ is even, .