We call a function $g$ special if $g(x)=a^{f(x)}$ (for all $x$) where $a$ is a positive integer and $f$ is polynomial with integer coefficients such that $f(n)>0$ for all positive integers $n$. A function is called an exponential polynomial if it is obtained from the product or sum of special functions. For instance, $2^{x}3^{x^{2}+x-1}+5^{2x}$ is an exponential polynomial. Prove that there does not exist a non-zero exponential polynomial $f(x)$ and a non-constant polynomial $P(x)$ with integer coefficients such that $$P(n)|f(n)$$for all positive integers $n$.
Problem
Source: Iran MO 3rd round 2016 finals - Number Theory P2
Tags: number theory, function, algebra, polynomial
05.09.2016 08:14
Any solutions?
05.09.2016 08:40
05.09.2016 21:57
Nice problem! As usual, Iran never fails in making elegant number theory problems! Solution: Let $n$ be a sufficiently big number and $p$ be a prime dividing $P(n)$. Notice that $p \mid P(n+k\cdot p)$ for all integers $k$. However, by Fermat's Little theorem, $F(n) \equiv F(m) \bmod p$ for all $m \equiv n \bmod p-1$. Thus, $F(n+k\cdot p) \equiv F(n+k) \bmod p$ and we set $k \equiv -n \bmod p-1$ which would give that on one hand, $p \mid P(n+k\cdot p)$ and the condition shows that $p \mid F(n+k\cdot p)$ yielding that $p \mid F(0)$. We obtain that $p$ is bounded, a contradiction to Schur's theorem unless $P$ is a constant polynomial, which is not a possibility as per the given statement. The result follows.