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
K.N
05.09.2016 08:14
Any solutions?
bgn
05.09.2016 08:40
Since $P(x)$ is a non-constant polynomial, there exists infinitely many prime numbers like $q_i$ and integer $\alpha _{i}$ such that $q_{i}|P(\alpha _{i})$
Assume that: $f(x)=\sum_{i=1}^{M}\prod_{j=1}^{i}a_j^{f_j(x)}$
We can choose a large $q_i$ so that $\forall j: q_i>a_j$
Now consider a positive integer $n$ satisfying:
$n\equiv \alpha _{i} \pmod {q_i}$
$n \equiv c \pmod {q_i-1}$ where $c$ is a positive integer such that $f(c) \neq 0$ ( $n$ exists since $\text{gcd}(q_i,q_i-1)=1$)
We have: $q_i|P(n)|f(n)=\sum_{i=1}^{M}\prod_{j=1}^{i}a_j^{f_j(n)}$
Note that $f(n) \equiv f(c) \pmod {q_i}$ (because $f_j(n) \equiv f_j(c) \pmod {q_i-1}$)
So we have : $q_i|f(c)$ for infinitely many prime numbers $q_i$. Take $q_i$ large enough so that $|f(c)|<q_i$
Therefore $q_i|f(c)$ is only possible when $f(c)=0$. Contradiction.
anantmudgal09
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.