Comment. A word or two on the origin of this problem is in order. The problem initially chosen for Day 4, P1 was N1 from the Shortlist, but understandably, none of us were very happy with that choice. This problem was born out of sheer spite against N1 as a desperate last-minute attempt to replace it with anything better (which is pretty much any semi-decent NT problem). It took us (mostly Anant, with others giving moral support) about an hour to go from "darn we need a better problem" via "how hard can it be to make a better problem" to "bam, here's a better problem", all thanks to our combined malice towards N1.

My favourite from the Indian TSTs. Kayak wrote: Determine all non-constant monic polynomials $f(x)$ with integer coefficients for which there exists a natural number $M$ such that for all $n \geq M$, $f(n)$ divides $f(2^n) - 2^{f(n)}$ Proposed by Anant Mudgal Solution. As $f$ is non-constant polynomial and $M$ is finite, number of primes dividing one of $f(M),f(M+1),\ldots$ is infinite from Schur's theorem. Say $p$ is a prime from one of the primes. We have \[p\mid f(n)\implies p\mid f(n+p)\mid f(2^{n+p}) - 2^{f(n+p)} \equiv f(2^{n+1})-2^{f(n+1)} \pmod p.\] This gives us $p\mid f(2^{n+k}) - 2^{f(n+k)}$ for all naturals $k$. Further taking the modulo again gives us $p\mid f(2^{n+k \pmod {p-1}}) - 2^{f(n+k \pmod {p-1})}$, so $p\mid f(2^{n}) - 2^{f(n)}$ for all $n$. Therefore we get $f(2^n) = 2^{f(n)}$ for all non-negative integers $n$. Now we have $2^k \mid 2^{k+n} \mid f(2^{k+n}) - f(0) = 2^{f(k+n)} - f(0)$ for all non-negative integers $n,k$. Now for any given $k$, as $f$ has leading term positive and $f$ is non-constant, we can pick a sufficiently large $n$ such that $f(n+k)>k$. Therefore $2^k \mid 2^{f(n+k)} - f(0)$, so $2^k \mid f(0)$ for all $k$ which gives us $f(0) = 0$. Now using this in $f(2^n) = 2^{f(n)}$, we get $f(2^n) = 2^n$. As $f$ is polynomial this gives us $f(x) = x$ is the only solution. $~\square$

Really nice problem Here's quite a wordy solution. $\textbf{Lemma 01. } \text{Suppose for some} \ n \ge M, \text{we have an odd prime} \ p \ \text{such that} \ p | f(n), \text{then we must have} \ p | f(2^m) - 2^{f(m)} \ \text{for all} \ m \ge n$. Proof. Notice that since $p | f(n+kp)$ for all $k \in \mathbb{N}$, we have \[ p | f(n+kp) | f(2^{n + kp}) - 2^{f(n+kp)} \]Using the fact that $2^{p - 1} \equiv 1 \ (\text{mod} \ p )$. We conclude that $p | f(2^{n+k}) - 2^{f(n+k)}$ for all $k \in \mathbb{N}$, proving our claim. $\textbf{Lemma 02:} f(2^q) = 2^{f(q)} \ \text{for any} \ q \in \mathbb{N}_0$. Proof. Now, take $m = a(p - 1) + q$ in Lemma 01 for any $q \in \mathbb{N}_0$ and a sufficiently large $a$. By Fermat Little, this reduces to \[ p | f(2^q) - 2^{f(q)} \]for any $q \in \mathbb{N}_0$. Note that since $f \in \mathbb{Z}[x]$ is non constant, then by $\textit{Schur}$ Theorem, there exists infinitely many primes $p$ such that there exists $n$ satisfying $p | f(n)$, $n \ge M$. This results $f(2^q) = 2^{f(q)}$ for all $q \in \mathbb{N}_0$. $\textbf{Lemma 03:} f(n) \ge n, n \in \mathbb{N}_0$ Proof. Since $f$ is monic, then for arbitrarily large $m$, we have $f(m) > f(n)$ for every $m > n$. Take such $m$ and take any $n$ such that $m > n$: we have \[ 2^n(2^{m-n} - 1) = 2^m - 2^n | f(2^m) - f(2^n) = 2^{f(m)} - 2^{f(n)} = 2^{f(n)} (2^{f(m)-f(n)} - 1)\]Therefore, we must have $f(n) \ge n$ for every $n \in \mathbb{N}_0$. $\textbf{Lemma 04:} f(0) = 0$ Proof. Suppose $f(0) \ge 1$, then we have $f(1) \equiv f(2^0) = 2^{f(0)} $. This results $2 | f(1)$. This also results $f(2) \equiv f(2^1) = 2^{f(1)}$ is divisible by 2, which gives us $f(n)$ is divisible by $2$ for all $n \in \mathbb{Z}$. Therefore, we could write $f(n) = 2g(n), n \in \mathbb{Z}$. Now, notice that we could write $\textbf{Lemma 02}$ back as $g(2^q) = 2^{2g(q) - 1}$. Note that since $g$ is integer - valued polynomial in $\mathbb{Z}$, then we couldn't have $g(q) = 0$ for any $q \in \mathbb{N}$. This results that $g(x)$ is completely divisible by $2$ for any $x \in \mathbb{Z}$. Thus, there exists polynomial $h(x)$ such that $g(n) = 2h(n)$ for all $n \in \mathbb{Z}$. Continuing this, we will have $v_2 (f(n)) = \infty$, which is a contradiction. Since $f(0) \ge 0$, then we must have $f(0) = 0$. To finish this, note that $f(0) = 0$, by induction one can prove that $f(x) = x$ for all $x = 2^{2^{2^{\dots}}}$, thus there are infinitely many zeroes of the polynomial $e(x) = f(x) - x$, which means that $e(x)$ is the zero polynomial. Therefore, $f(x) = x$. Checking back to the original problem, this clearly satisfies.

Lemma: Let $ f(x) \in \mathbb{Z} [x]$, $deg f(x) \geq 1$, $A=\{p: p \mid f(n), n\in \mathbb{Z}_+, p \text{ is a prime} \}$, then $|A|=+\infty$. Proof: If $A=\{p_1, p_2, \cdots, p_t\}$, let $f(x)=a_nx^n+\cdots+a_1x+c$, $f(0)=c \neq 0$, $$f(cp_1 p_2 \cdots p_t)=c[a_nc^{n-1}(p_1 p_2 \cdots p_t)^n+\cdots+a_1(p_1 p_2 \cdots p_t)+1]$$has a prime factor which is different from $p_1, p_2, \cdots, p_t$, a contradiction. Now back to finish it: For any fix $N \in \mathbb{Z}_+$, we know there exist lagre enough $n$, such that $f(n)$ has a prime factor $p>max\{2, f(2^N)-2^{f(n)}\}$. Now we select $k$, $kp+n=N(mod (p-1))$. Clearly, $p \mid f(n+kp)$, then $p \mid f(2^{n+kp})-2^{f(n+kp)}$, hence $p \mid f(2^N)-2^{f(n)}$(beacuse $x-y \mid f(x)-f(y)$). We can get $f(2^N)=2^{f(N)}$ for any $N$, $deg f=n$, $\frac{2^{nN}}{2^{N^{n}}}\rightarrow 1(N\rightarrow +\infty)$, then $deg f(x)=1$, let $f=ax+b$, we can prove $a=1$, $b=0$. $f(x)=x$.

We have that if a prime divides both $f(n)$ and $f(2^n)$ , then $p=2$.Now , let $p$ be an odd prime dividing $f(2^t)$ for some natural $t$.Then $$p|f(2^t+pk)$$Now take a $k$ such that $p-1|2^t-t+k$.Then $f(2^t+pk) \equiv( 2^t )\equiv 0\pmod p$.This means that $p=2$. Thus $f$ maps perfect powers of $2$ to perfect powers of $2$.Then , since $f$ is non-constant , there fore we get that $v_2(f(0))$ increases indefinitely , and thus $f(0)=0$.Similarly , taking the power of two common out of $f$, we will get that the coefficient of $x$ is also $0$ , and so on.Thus we get that $f(x)= x^n$ for some $n$ .Now , taking $p$ to be an odd prime and putting it inthe equation , and using FLT , we will get easily that $n=1$.

Very cute integer polynomial problem! Probably easy for the pros, but I had a really nice time solving it. It took me one hour to finish along with write-up. Solution: The answer is $f \equiv x$ which can be clearly seen to work. We head towards the direction now. For some $n > M$, pick $p \mid f(n)$. This would yield \[p \mid f(n) \implies p \mid f(n+kp) \mid f(2^{n+kp}) - 2^{f(n+kp)}.\]Carefully reducing the entire extreme RHS gives \[p \mid f(2^{n+k}) - 2^{f(n+k)}.\]For instance putting $k = -n$, would yield that any arbitrary prime divisor of $f(n)$ is bounded. This is impossible due to Schur's Theorem. Therefore we conclude that $f(2^n) = 2^{f(n)}$ for any $n \in \mathbb{Z}$. Consider the following equation \[\frac{f(2^{n+1})}{f(2^n)} = 2^{f(n+1)-f(n)}.\]Observe that $\mathcal{O}(\text{LHS})$ is constant and $\mathcal{O}(\text{RHS}) = n^{\deg(f)-1}$. This forces $f$ to be linear when you take $n \to \infty$. A quick substitution of $f(x) = ax+b$ into $f(2^n) = 2^{f(n)}$ gives \[2^n\cdot a + b = 2^{an+b}.\]Since $2^n \mid b$ for arbitrarily large $n$, we must have $b = 0$. Finally taking $\log_2$, we can conclude $a = 1$ and the solution is complete. $\blacksquare$

Ankoganit wrote:

Comment. A word or two on the origin of this problem is in order. The problem initially chosen for Day 4, P1 was N1 from the Shortlist, but understandably, none of us were very happy with that choice. This problem was born out of sheer spite against N1 as a desperate last-minute attempt to replace it with anything better (which is pretty much any semi-decent NT problem). It took us (mostly Anant, with others giving moral support) about an hour to go from "darn we need a better problem" via "how hard can it be to make a better problem" to "bam, here's a better problem", all thanks to our combined malice towards N1. When we find g is a const function why not use g=2^k for some k rather than taking g=1

Great polynomial nt problem

Here we go: Claim: $f(2^n) = 2^{f(n)}$ for all $n \ge 1$. Let $p$ be a prime, $p|f(n)$ which gives: $p|f(2^n)-2^{f(n)}$. Now: replacing $n \to n+p$, we get: $p|f(2^{n+1})-2^{f(n+1)}$. Therefore: $p|f(2^n)-2^{f(n)}$ for all $n \ge 1$. Due to Schur's theorem, there exists infinitely many primes dividing $f(n)$. Consider a value of $n \in \mathbb N$ and fix it. Taking $p$ to be a large prime, we get: $f(2^n) = 2^{f(n)}$ for all $n \ge 1$. Claim: $f(0)=0$ Notice that: $2^n | 2^{n+k} | f(2^{n+k})-f(0) = 2^{f(n+k)} - f(0)$. Taking the value of $n$ large enough: if $f(n+k) < n$ for all sufficiently large $n$, then $2^n > 2^{f(n+k)} - f(0)$ which contradicts. Thus: $f(n+k) > n$ for all sufficiently large enough values of $n$. Therefore: $2^n | f(0)$ for all sufficiently large enough values of $n$ which implies $f(0)=0$. Plugging $f(0)$ and recursively computing over the equation: $f(2^n) = 2^{f(n)}$, we get $f(2^{2^k}) = 2^{2^k}$ for all $k \ge 0$. Since $f$ is a polynomial, we have: $f(x)=x$ and we are done.