If $ P(x),Q(x),R(x)$, and $ S(x)$ are all polynomials such that \[ P(x^5)+xQ(x^5)+x^2R(x^5)=(x^4+x^3+x^2+x+1)S(x),\] prove that $ x-1$ is a factor of $ P(x)$.
Problem
Source: 1976 USAMO Problem 5
Tags: algebra, polynomial, linear algebra, matrix
xpmath
04.04.2010 06:53
Let $ w$ be a fifth root of unity not equal to $ 1$. We substitute $ 1, w, w^2, w^3,$ and $ w^4$ one at a time for $ x$ and add up the five resulting equations.
By the well known fact that $ 1+w+w^2+w^3+w^4=0$ and that $ w^5=1$, the left hand side reduces to $ 5P(1)$ while the right hand side is $ 0$, so $ P(1)=0$, meaning $ x-1$ is a factor of $ P(x)$.
math154
04.04.2010 07:51
that just gives $ 5P(1) = 5S(1)$... so we adjust a bit by adding up\[ x P(x^5) + x^2 Q(x^5) + x^3 R(x^5) = x(x^4 + x^3 + x^2 + x + 1) S(x)\]for the five roots $ \omega^k$ to get
\[ 0 = P(1)\sum_{k = 0}^{4}{\omega^k} + Q(1)\sum_{k = 0}^{4}{\omega^{2k}} + R(1)\sum_{k = 0}^{4}{\omega^{3k}} = 5S(1) = 5P(1).\]
xpmath
04.04.2010 17:08
Blah yeah I knew I'd make some mistakes last night anyway.
Kunihiko_Chikaya
04.04.2010 17:16
Can we generalize the problem?
JSGandora
23.08.2012 23:30
Let $\omega=$ a primitive fifth root of unity, then the five equation that result from plugging in $\omega^k$ for $x$ for $k=\{1, 2, 3, 4, 5\}$ are
\begin{align}
P(1)+\omega Q(1)+\omega^2 R(1)&=0 \\
P(1)+\omega^2 Q(1)+\omega^4 R(1)&=0\\
P(1)+\omega^3 Q(1)+\omega R(1)&=0\\
P(1)+\omega^4 Q(1)+\omega^3 R(1)&=0\\
P(1)+ Q(1)+ R(1)&=5S(1).
\end{align}
Adding all the equations yields $P(1)=S(1)\implies P(1)=\frac{Q(1)+R(1)}4$.
$(1)-(2)+(4)-(3)$ yields $Q(1)=R(1)=b$. Let $P(1)=a$ then from the first two equations we have
$(\omega-\omega^4)b=0$. Since $\omega-\omega^4\neq 0$, we have $b=Q(1)=R(1)=0$ so $P(1)=0$ which means $x-1$ is a factor of $P(1)$ as desired.
Kunihiko_Chikaya
24.08.2012 04:02
!976 USA MO, Problem 5.
Kolumbus
18.03.2013 12:04
Sorry, but why can't I just
consider the linear equations (1), (2), (3) in the solution by JSGandora? By computing the determinant \[\begin{vmatrix}1&\omega&\omega^2\\1&\omega^2&\omega^4\\1&\omega^3&\omega\end{vmatrix}=\omega^3+2-2\omega^2-\omega^4\neq0,\] one can immediately deduce that $P(1)=Q(1)=R(1)=0$. Correct?
AkshajK
22.12.2014 19:36
bump; also curious about above question
va2010
29.09.2015 02:28
Here's a faster solution. Let $\omega$ be a primitive $5$th root of unity, and observe that for $x = 1, 2, 3, 4$, $P(1)+\omega^xQ(1)+\omega^{2x}R(1) = 0$. Hence $\omega, \omega^2, \omega^3$, and $\omega^4$ are roots of the quadratic equation $P(1)+xQ(1)+x^2R(1)$. A quadratic null at 3 different places must be null everywhere, implying $R(1)=Q(1)=P(1)=0$, so we're done.
OlympusHero
15.04.2021 00:13
Note that if $1$ is a root of $P(x)$, then $x-1$ must be a factor of $P(x)$. Plugging in $x=1$ to the original equation, we get $P(1)+Q(1)+R(1)=5S(1)$. Plugging in $x=0$ gives $P(0)=S(0)$.
Is there a way to conclude without using roots of unity or something like that? Not too familiar with such things.
lrjr24
15.04.2021 02:59
OlympusHero wrote:
Note that if $1$ is a root of $P(x)$, then $x-1$ must be a factor of $P(x)$. Plugging in $x=1$ to the original equation, we get $P(1)+Q(1)+R(1)=5S(1)$. Plugging in $x=0$ gives $P(0)=S(0)$.
Is there a way to conclude without using roots of unity or something like that? Not too familiar with such things. I don’t think there is a way without roots of unity.
jasperE3
22.04.2021 06:13
Let $K(x)$ denote the given assertion, and let $\omega$ be a primitive $5$th root of unity. $$\begin{cases}K(1)&\Rightarrow P(1) P(1)+Q(1)+R(1)=5S(1)\\ K(\omega)&\Rightarrow P(1)+\omega Q(1)+\omega^2R(1)=0\\ K\left(\omega^2\right)&\Rightarrow P(1)+\omega^2Q(1)+\omega^4R(1)=0\\ K\left(\omega^3\right)&\Rightarrow P(1)+\omega^3Q(1)+\omega R(1)=0\\ K\left(\omega^4\right)&\Rightarrow P(1)+\omega^4Q(1)+\omega^3R(1)=0\end{cases}$$Adding up all of these yields $P(1)=S(1)$. Hence: $$\begin{cases}Q(1)+R(1)=4S(1)\\ \omega Q(1)+\omega^2R(1)+S(1)=0\\ \omega^2Q(1)+\omega^4R(1)+S(1)=0\\ \omega^3Q(1)+\omega R(1)+S(1)=0\\ \omega^4Q(1)+\omega^3 R(1)+S(1)=0\end{cases}$$which is more than enough. Solving the system, we easily get $P(1)=0$, which completes the proof. $\square$
Math_Is_Fun_101
09.01.2022 04:44
lrjr24 wrote: OlympusHero wrote:
Note that if $1$ is a root of $P(x)$, then $x-1$ must be a factor of $P(x)$. Plugging in $x=1$ to the original equation, we get $P(1)+Q(1)+R(1)=5S(1)$. Plugging in $x=0$ gives $P(0)=S(0)$.
Is there a way to conclude without using roots of unity or something like that? Not too familiar with such things. I don’t think there is a way without roots of unity. There is a way. Let $T\colon\mathbb R[x]\to\mathbb R^5$ be the function given by \[ \sum a_kx^k\mapsto\left(\sum_{5\mid k}a_k,\sum_{5\mid k-1}a_k,\ldots,\sum_{5\mid k-4}a_k\right). \]It is clear that \[ T(P(x^5)+xQ(x^5)+x^2R(x^5))=(P(1),Q(1),R(1),0,0). \]It is also easy to see that \[ T((x^4+x^3+x^2+x+1)S(x))=(S(1),S(1),S(1),S(1),S(1)). \]Since $P(x^5)+xQ(x^5)+x^2R(x^5)=(x^4+x^3+x^2+x+1)S(x)$, these two must be equal, giving \[ P(1)=Q(1)=R(1)=S(1)=0. \]Hence, $x-1\mid P(x)$. $\blacksquare$
huashiliao2020
14.04.2023 08:25
x^5 and $x^4+x^3+x^2+x+1=(x^5-1)/(x-1)$ and the fact that if x-1 is a factor of P(x) suggests P(1)=0 gives suggestions to find ways with powers of 5 and 1. With experience, you will find motivation to consider the roots of unity. Now summing over $1, x, x^2, …, x^4$ with x=a fifth root of unity not equal to 1, and $x^5=1$, then $5P(1)+$ (in some order, 1, x, …, x^4 each appear once in each root of unity) $5(x+x^2+…+1)Q(1)+5(x^2+x^3+…+x)R(1)=5(x^4+x^3+x^2+x+1)S(x)$, then b/c $x^4+x^3+…+1=(x^5-1)/(x-1)=0$, all of those cancel out as being equal to 0 and we get $5P(1)=0$, as desired. $\blacksquare$