Let $f(x)=x^n + a_{n-1}x^{n-1} + ...+ a_0 $ be a polynomial of degree $ n\ge 1 $ with $ n$ (not necessarily distinct) integer roots. Assume that there exist distinct primes $p_0,p_1,..,p_{n-1}$ such that $a_i > 1$ is a power of $p_i$, for all $ i=0,1,..,n-1$. Find all possible values of $ n$.
Problem
Source: Baltic Way 2015
Tags: algebra, polynomial, number theory
ngv
08.11.2015 21:55
Wolowizard wrote: Let $f(x)=x^n + a_{n-1}x^{n-1} + ...+ a_0 $be a polynomial of degree$ n\ge 1 $with$ n$ (not necessarily distinct) integer roots. Assume that there exist distinct primes $p_0,p_1,..,p_{n-1}$ such that $a_i > 1$ is a power of $p_i$, for all$ i=0,1,..,n-1$. Find all possible values of$ n$. Let the roots be $r_0,\ldots,r_{n-1}$ and $a_i=p_i^{e_i}$. From Vietta's formula, $r_0\cdots r_{n-1}=(-1)^na_0=(-1)^np_0^{e_0}$. Since $r_i$ is integer, $r_i=p_0^{b_i}$ for some $b_i$ so that $b_0+\ldots+b_{n-1}=e_0$. But then \[r_0+\ldots+r_{n-1}=-a_{n-1}\]\[p_0^{b_0}+\ldots+p_0^{b_{n-1}}=-p_{n-1}^{e_{n-1}}\]Since $e_i>0$, if $m=\min(b_0,\ldots,b_{n-1})>0$ then $p_0$ divides $p_{n-1}$, a contradiction. Thus, $m=0$ and $r_i=p_0^0=1$ is a root of $f(x)$ for some $i$. $f(1)=0$ implies $1+a_0+\ldots+a_{n-1}=0$, which is a contradiction since $a_i>1$. Edit: I just remembered the constraint the roots are not necessarily distinct. In that case, this solution may fail.
Gryphos
11.11.2015 22:08
The possible values for $n$ are $1, 2, 3, 4$.
For $n=1$ take for example $f(x)=x+2$ with root $x_1=-2$.
For $n=2$ take $f(x)=x^2+3x+2=(x+1)(x+2)$ with roots $x_1=-1, x_2=-2$.
If $n=3$, take $f(x)=x^3+7x^2+11x+5=(x+1)^2(x+5)$ with roots $x_1=x_2=-1$ and $x_3=-5$.
Finally for $n=4$ we can take $f(x) = x^4+11x^3+27x^2+25x+8 = (x+1)^3(x+8)$ with roots $x_1=x_2=x_3=-1$ and $x_4=-8$.
Now let $n>4$, I will prove that there are no solutions in this case. First, it is clear that all roots of $f$ have to be negative since all its coefficients are strictly positive. This means there exist (not necessarily distinct) positive integers $y_1, \ldots, y_n$ with $f(x)=(x+y_1)(x+y_2) \cdots (x+y_n)$. We have $a_0=p^k = y_1 y_2 \ldots y_n$ for some prime $p$, hence all $y_i$ are powers of $p$. If at least two of the $y_i$ are divisble by $p$, we get that $a_1$ is also divisible by $p$, which is impossible. Thus we can w.l.o.g. assume that $y_1=a_0=p^k$ and $y_2=y_3=\cdots = y_n=1$.
Now we easily get $a_k={n-1 \choose k-1} + a_0{n-1 \choose k}$ by computing the coefficients. In particular, $2a_2=2(n-1)+a_0(n-1)(n-2)$ is divisble by $n-1$, as well as $2a_{n-2} = (n-1)(n-2)+a_0(n-1)$. But since $n-1 > 2$, this implies that $a_2$ and $a_{n-2}$ have a common divisor greater than $1$. On the other hand, we have $n-2 \not= 2$ because of $n>4$, and thus $a_2$ and $a_{n-2}$ have to be powers of different primes. This is a contradiction, hence the problem is solved.
rafaello
14.08.2021 00:37
For $n=1$, take $f(x)=x+3$. For $n=2$, take $f(x)=x^2+9x+8$. For $n=3$, take $f(x)=x^3+5x^2+7x+3$. For $n=4$, take $f(x)=x^4+5x^3+9x^2+7x+2$. Now, we assume that $n\geq 5$. We write our polynomial $P$ as $$P(x)=(x-x_1)(x-x_2)\ldots(x-x_n),$$where $x_i$ denotes the integer roots of our polynomial. Note that by the condition, we must have $(-1)^nx_1x_2x_3\ldots x_n=a_0=p_{0}^{k}$. If $\exists i,j$, such that $p_0\mid x_i,x_j$, we get that $p_0\mid \displaystyle \sum_{i}\frac{(-1)^{n-1}x_1x_2\ldots x_n}{x_i}=a_{1}$, which contradicts the distinctness of our primes. Thus only one $x_i$ is divisible by $p_0$. Therefore other $x_i$'s are either $1$ or $-1$. But as all the coefficients $a_i$ are positive, $1$ and $p_0^k$ are not the roots of $f(x)$. Hence, wlog $x_n=-p_0^k$ and $x_1=x_2=\ldots=x_{n-1}=-1$. Now note that $$a_2=\sum_{i\neq j} x_ix_j=(n-1)p_0^k+\frac{n(n-1)}{2}$$and $$a_{n-2}=(-1)^{n-2}\sum_{i\neq j}\frac{x_1\ldots x_n}{x_i x_j}=\frac{n(n-1)}{2}p_0^k+(n-1).$$Notice that there is a prime, which divides both $n-1$ and $\frac{n(n-1)}{2}$ as $n-1\neq 1,2$. Therefore $a_{n-2}$ and $a_2$ are the same prime power, which contradicts the distinctness of our primes. No $n\geq 5$. We are done.