Balkan Mathematical Olympiad competition problems

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 \pmod{Q(n)}$$
$$n^{Q(n)-n} + (-n)^n \equiv 0 \pmod{Q(n)}$$
Let $Q(0) = a_0$. Assume for the sake of contradiction that $a_0 \neq 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 \pmod{Q(n)} \implies n^{Q(n)-2n} - 1 \equiv 0 \pmod{Q(n)},$$
that is
$$n^{Q(n)-2n} \equiv 1 \pmod{Q(n)} \quad (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 \pmod{p}$$
$$m \equiv n_0 \pmod{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 \pmod{p},$$
implying $\text{ord}_p(m) \mid Q(m) - 2m$. Since $m \equiv n \pmod{p}$ and $m \equiv n_0 \pmod{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 \pmod{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 \qquad (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 $\deg(R(x)) < \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_iQ(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$:
$$d_i = \frac{f_i}{D} + r_i \\ \frac{d_i D - f_i}{D} = r_i.$$
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) = dQ_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 \pmod{p}$ be an even integer such that

$k > N$. Then $k^{Q(k)-k} + (-k)^k \equiv 2 \pmod{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 \pmod{Q(n)}$$
$$n^{Q(n)-2n} \equiv -1 \pmod{Q_1(n)}$$
$$n^{2(Q(n)-2n)} \equiv 1 \pmod{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 \pmod{p}$ yields
$$n^{a_0} \equiv -1 \pmod{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 \pmod{p}$$
In either case we have
$$n^{|a_0|} \equiv -1 \pmod{p}$$
$$n^{2^l} \equiv -1 \pmod{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 \pmod{Q_1(n)}$$
$$(n^2 - 1)(n^2 + 1) \equiv 0 \pmod{Q_1(n)}$$
$$n^{2^l} \equiv -1 \pmod{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 \pmod{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 \pmod{p}$. It follows that $p \mid n_0^{n_0R(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) \neq 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 \pmod{2^s n^k}.$$
However, if $s \ge 4$, let $n \equiv 3 \pmod{16}$ then, $Q(n) - n \equiv 5 \pmod{8}$,
$$3^5 + (-3)^3 \equiv 8 \pmod{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 \pmod{8}$, implying the claim.
Finally, $Q(n) > n$ is obviously satisfied for all such $s, k$ and the result follows.