42nd Balkan Mathematical Olympiad

The solutions are $P(n)=1$ and $P(n)=2^s{n}^k-n$ for $0\le s\le 3$ and $k\ge 1$, excluding $P(n)=0$.

Firstly, we denote $Q(n)=P(n)+n$. We then have $Q(n)>n$ for all $n>N$. Note that the condition can be rewritten as $$n^{Q(n)-n}+(Q(n)-n{)}^n\equiv 0(\mathrm{mod}Q(n))$$ $$n^{Q(n)-n}+(-n{)}^n\equiv 0(\mathrm{mod}Q(n))$$ Let $Q(0)=a_0$. Assume for the sake of contradiction that $a_0\ne 0$ and let $n>N$ be an odd positive integer such that $(a_0,n)=1$. Notice that $(Q(n),n)=1$, since if some prime $p$ divides both $n$ and $Q(n)$, it would also divide $a_0$, contradiction. Therefore we have $$n^n(n^{Q(n)-2n}-1)\equiv 0(\mathrm{mod}Q(n))⟹n^{Q(n)-2n}-1\equiv 0(\mathrm{mod}Q(n)),$$ that is $$n^{Q(n)-2n}\equiv 1(\mathrm{mod}Q(n))(1)$$ Let $p\mid Q(n)$ be an odd prime (we know that $p$ doesn't divide $n$). It follows that ${\text{ord}}_p(n)\mid Q(n)-2n$. Let $n_0>N$ be any odd integer. By the Chinese remainder theorem there exists an integer $m>N$ such that $$m\equiv n(\mathrm{mod}p)$$ $$m\equiv n_0(\mathrm{mod}p-1).$$ Therefore, $p\mid Q(m)$. Since $n_0$ is odd and $p\nmid n$, it follows that $m$ is odd and $p\nmid m$. Therefore we can conclude that (in a similar fashion as we have done for $n$): $$m^{Q(m)-2m}\equiv 1(\mathrm{mod}p),$$ implying ${\text{ord}}_p(m)\mid Q(m)-2m$. Since $m\equiv n(\mathrm{mod}p)$ and $m\equiv n_0(\mathrm{mod}p-1)$, it follows that ${\text{ord}}_p(n)\mid Q(n_0)-2n_0$. Therefore $${\text{ord}}_p(n)\mid Q(m)-2m,$$ for all odd $m>M$, but due to the periodicity of the polynomial $Q$ modulo ${\text{ord}}_p(n)$, this in fact means that the above holds for any odd integer $m$. Now we have that $${\text{ord}}_p(n)\mid \text{gcd}(Q(1)-2,Q(3)-6,\dots ,Q(2i+1)-2(2i+1),\dots ).$$ Denote the previous gcd with $G$. Let $p\mid G$ be an odd prime. It follows that $p\mid Q(p)-2p$, implying $p\mid a_0$. Let $k$ be a large enough positive integer. Then $v_p(Q(a_0^k)-2a_0^k)=v_p(a_0)$. Therefore $v_p(G)\le v_p(a_0)$ and so it follows that $G\mid 2^t{a}_0$ for some integer $t\ge 0$. Coming back to our original $n$ we get that $$n^G\equiv 1(\mathrm{mod}p).$$

From (1) and Lifting The Exponent lemma it follows that $$v_p(n^{Q(n)-2n}-1)=v_p((n^G{)}^{\frac{Q(n)-2n}{G}}-1)=v_p(n^G-1)+v_p(\frac{Q(n)-2n}{G})\ge v_p(Q(n)).$$ As $p\mid Q(n)$ and $p\nmid n$, we get $v_p(\frac{Q(n)-2n}{G})=0$. If $2\mid Q(n)$ Lifting The Exponent lemma for $p=2$ yields $v_2(n^{Q(n)-2n}-1)=v_2(n^2-1)+v_2(Q(n)-2n)-1\ge v_2(Q(n))$. If $4\mid Q(n)$, it follows that $2\nmid Q(n)-2n$, yielding $v_2(n^2-1)\ge v_2(Q(n))$. If $2\nmid Q(n)$, $v_2(n^2-1)\ge v_2(Q(n))$ still holds. If $2\mid Q(n)$, it follows that $2\mid G$, and we get $v_p(n^G-1)\ge v_p(Q(n))$ for all primes $p\mid Q(n)$, implying $Q(n)\mid n^G-1$ (2). As $G$ is independent of $n$, we get $$Q(n)\mid n^G-1(2)$$ for every odd integer $n>N$ such that $(a_0,n)=1$. We say that a polynomial with integer coefficients is primitive if the greatest common divisor of its coefficients is 1. Lemma. Let $P(x),Q(x)\in \mathbb{Z}[x]$ be primitive such that $Q(n)\mid P(n)$ for infinitely many positive integers $n$. Then there exists a polynomial $F(x)\in \mathbb{Z}[x]$ such that $P(x)=Q(x)F(x)$. Proof. By the polynomial division algorithm there exist polynomials $F(x),R(x)\in \mathbb{Q}[x]$ such that $P(x)=Q(x)F(x)+R(x)$ and $\mathrm{deg}(R(x))<\mathrm{deg}(Q(x))$. Dividing the expression by $Q(x)$ yields $$\frac{P(x)}{Q(x)}=F(x)+\frac{R(x)}{Q(x)}.$$ Let $n_1,n_2,\dots$ be a sequence of positive integers such that $Q(n_i)\mid P(n_i)$ and let $P(n_i)=d_{i}Q(n_i)$ for $d_i\in \mathbb{Z}$, for all $i\in \mathbb{N}$. Let $D$ be the least common multiple of the denominators of the coefficients of $F(x)$. Then we can write $F(n_i)=\frac{f_i}{D}$ and $\frac{R(n_i)}{Q(n_i)}=r_i$ for $f_i\in \mathbb{Z},r_i\in \mathbb{Q}$. We get the following equation for every $i$: $$\begin{gathered} d_i=\frac{f_i}{D}+r_i \\ \frac{d_{i}D-f_i}{D}=r_i. \end{gathered}$$ As ${\lim }_{i\to \infty }{r}_i=0$, there has to exist a large enough positive integer $j$ such that $0<|r_j|<\frac{1}{D}$. Therefore $R(x)\equiv 0$ and $P(x)=Q(x)F(x)$. We are left to prove that $F$ has integer coefficients. Let $a$ be the greatest common divisor of the numerators of the coefficients of $F(x)$ and let $b$ be the least common multiple of the denominators of the coefficients of $F(x)$. We can assume $(a,b)=1$. Therefore $F(x)=\frac{a}{b}{F}_1(x)$ for some primitive polynomial $F_1(x)\in \mathbb{Z}[x]$. Now we get $\frac{b}{a}P(x)=Q(x)F_1(x)$. Since $\frac{b}{a}P(x)$ is a polynomial with integer coefficients and $(a,b)=1$, it follows that $a$ divides all coefficients of $P(x)$. Therefore $a=1$ (since $P$ is primitive). As $Q(x)$ and $F_1(x)$ are primitive, $bP(x)$ is primitive by Gauss' lemma. Therefore $b=1$ and $F(x)\in \mathbb{Z}[x]$, as desired. $\square$ Let $Q(x)=d{Q}_1(x)$, where $d$ is a positive integer (possibly $d=1$) and $Q_1(x)\in \mathbb{Z}[x]$ is primitive. Assume there exists an odd prime $p\mid d$ and let $k\equiv 1(\mathrm{mod}p)$ be an even integer such that

$k>N$. Then $k^{Q(k)-k}+(-k{)}^k\equiv 2(\mathrm{mod}p)$, so $p=2$, which is a contradiction. Therefore $d=2^l$ for some integer $l\ge 0$. Let $P_1(x)=x^G-1$. Since $Q_1(n)|P_1(n)$ for infinitely many positive integers $n$ and $P_1(x),Q_1(x)$ are primitive, by the above lemma there exists a polynomial $F(x)\in \mathbb{Z}[x]$ such that $P_1(x)=Q_1(x)F(x)$. In particular, $-1=P_1(0)=Q_1(0)F(0)$, so $Q_1(0)$ is either 1 or $-1$. Therefore $a_0$ is either $2^l$ or $-2^l$. Let $n>N$ be an even positive integer. If $p\mid Q(n)$ and $p\mid n$, it follows that $p=2$. Additionally, $v_2(Q(n))=v_2(d)=l$. The original condition yields $$2^l(n^{Q(n)-2n}+1)\equiv 0(\mathrm{mod}Q(n))$$ $$n^{Q(n)-2n}\equiv -1(\mathrm{mod}{Q}_1(n))$$ $$n^{2(Q(n)-2n)}\equiv 1(\mathrm{mod}{Q}_1(n))$$ Let $p\mid Q_1(n)$ be an odd prime ($p\nmid n$). Picking $n_0$ divisible by $p-1$ such that $n_0\equiv n(\mathrm{mod}p)$ yields $$n^{a_0}\equiv -1(\mathrm{mod}p).$$ If $a_0<0$, i.e. $a_0=-|a_0|$, then $$n^{|a_0|}+1=n^{-a_0}+1=\frac{n^{a_0}+1}{n^{a_0}}\equiv 0(\mathrm{mod}p)$$ In either case we have $$n^{|a_0|}\equiv -1(\mathrm{mod}p)$$ $$n^{2^l}\equiv -1(\mathrm{mod}p).$$ Therefore ${\text{ord}}_p(n)=2^{l+1}$. Using Lifting The Exponent lemma analogously as before (without the case $p=2$ as $2\nmid Q_1(n)$), we get: $$v_p(n^{2(Q(n)-2n)}-1)=v_p((n^{2^{l+1}}{)}^{\frac{2(Q(n)-2n)}{2^{l+1}}}-1)=v_p(n^{2^{l+1}}-1)+v_p(\frac{2(Q(n)-2n)}{2^{l+1}}).$$ Since $v_p(\frac{2(Q(n)-2n)}{2^{l+1}})=0$ (because $p\mid Q_1(n)$ so $p\mid Q(n)$ and $p\nmid n$), we get that $v_p(n^{2(Q(n)-2n)}-1)=v_p(n^{2^{l+1}}-1)\ge v_p(Q_1(n))$ and so: $$n^{2^{l+1}}\equiv 1(\mathrm{mod}{Q}_1(n))$$ $$(n^2-1)(n^2+1)\equiv 0(\mathrm{mod}{Q}_1(n))$$ $$n^{2^l}\equiv -1(\mathrm{mod}{Q}_1(n)),$$ where the last equation holds because $(n^2-1,Q_1(n))=1$ (since any prime $p$ that divides $Q_1(n)$ also divides $n^2+1$, and $p$ is odd). Thus $Q_1(n)\mid n^2+1$ for all even positive integers $n>N$. As $Q_1(x)$ and $x^2+1$ are primitive, by the lemma there exists a polynomial $F_1(x)\in \mathbb{Z}[x]$ such that $x^2+1=Q_1(x)F_1(x)$. Since $x^2+1$ is known to be irreducible and $Q_1(x)$ is eventually positive, it must hold that $Q_1(x)=x^2+1$. We return to odd values of $n$ once again. If $l\ge 1$, we obtain $G=2$ (it is immediate for $l>1$ and for $l=1$ it follows from $G\mid Q_1(1)$). Let $n>N$ be an odd positive integer. Divisibility (2) yields $$n^2\equiv 1(\mathrm{mod}{2}^l{n}^{2^l}+2^l),$$

Therefore $l=0$ and $Q(x)=x+1$, which is easily seen to be a solution to the problem (it gives $P(x)=1$). Now assume $a_0=0$. Let $Q(x)=xR(x)$ for some $R(x)\in \mathbb{Z}[x]$. The original condition after cancelling $n$ rewrites as $$R(n)\mid n^{n-1}(n^{nR(n)}-2n+(-1{)}^n).$$ Assume there exists an even integer $n>N$ and a prime $p\mid R(n)$ such that $p\nmid n$. Then $p\mid n^{nR(n)-2n}+1$. Let $n_0>N$ be an even integer such that $p-1\mid n_0$ and $n_0\equiv n(\mathrm{mod}p)$. It follows that $p\mid n_0^{n_{0}R(n_0)-2n_0}+1$ implying $p\mid 2$, which is false since $n$ is even. (3) Let $R(x)=x^{k-1}G(x)$ for some $G(x)\in \mathbb{Z}[x]$ such that $G(0)\ne 0$ and $k\ge 1$. If $G(x)$ is non-constant, by Schur's theorem there are infinitely many primes $p$ dividing $G(2m_p)$ for some $m_p\in \mathbb{N}$. For large enough such primes $p$ (and thus also $2m_p$), we have $p\nmid G(0)$ and thus $p\nmid 2m_p$, which is impossible by (3). Therefore $G(x)\equiv c$ for some constant $c$. It follows from (3) and eventual positivity of $Q(x)$ that $c=2^s$ for some integer $s\ge 0$, that is $Q(x)=2^s\cdot x^k$. We have $$n^{Q(n)-n}+(-n{)}^n\equiv 0(\mathrm{mod}{2}^s{n}^k).$$ However, if $s\ge 4$, let $n\equiv 3(\mathrm{mod}16)$ then, $Q(n)-n\equiv 5(\mathrm{mod}8)$, $$3^5+(-3{)}^3\equiv 8(\mathrm{mod}16),$$ which is a contradiction. Therefore, $s\le 3$. We will show that all pairs $(s,k)$ with $3\ge s\ge 0$ and $k\ge 1$ except for $s=0,k=1$ satisfy the problem's conditions ($s=0$ and $k=1$ fails since we need to have $Q(n)>n$ for $n>N$). If $n$ is even, $2^s{n}^k\mid n^{n-1}$ for large enough positive integers $n$. If $n$ is odd, $n^k\mid n^{n-1}$ for large enough positive integers $n$ and it remains to prove that $2^s\mid n^{2^s{n}^{k-2n}}-1$. For $s=0$ the divisibility is obvious and for $s\ge 1$ we have that $n^{2^s{n}^{k-2n}}=n^{2(2^{s-1}{n}^k-n)}\equiv 1(\mathrm{mod}8)$, implying the claim. Finally, $Q(n)>n$ is obviously satisfied for all such $s,k$ and the result follows.