Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1993 IMO Problems/Problem 1"

(Created page with "Let <math>f\left(x\right)=x^n+5x^{n-1}+3</math>, where <math>n>1</math> is an integer. Prove that <math>f\left(x\right)</math> cannot be expressed as the product of two non-co...")
 
(→‎Solution)
Line 9: Line 9:
 
From this fact, we have that there must exist a rational root of <math>f\left(x\right)</math>. The only candidates are <math>1</math>, <math>-1</math>, <math>3</math>, and <math>-3</math>, though. <math>f\left(1\right)=9\neq0</math>, <math>f\left(-1\right)=\pm4+3\neq0</math>, <math>f\left(3\right)=3^n+5\cdot3^{n-1}+3>0</math>, and <math>f\left(-3\right)=\pm\left(2\cdot3^n\right)+3\neq0</math>, so none of these work. Thus, there are no linear factors of <math>f\left(x\right)</math>.
 
From this fact, we have that there must exist a rational root of <math>f\left(x\right)</math>. The only candidates are <math>1</math>, <math>-1</math>, <math>3</math>, and <math>-3</math>, though. <math>f\left(1\right)=9\neq0</math>, <math>f\left(-1\right)=\pm4+3\neq0</math>, <math>f\left(3\right)=3^n+5\cdot3^{n-1}+3>0</math>, and <math>f\left(-3\right)=\pm\left(2\cdot3^n\right)+3\neq0</math>, so none of these work. Thus, there are no linear factors of <math>f\left(x\right)</math>.
  
−
In other words, <math>f\left(x\right)</math> cannot be expressed as <math>g\left(x\right)h\left(x\right)</math> for polynomials <math>g\left(x\right)</math> and <math>h\left(x\right)</math> in <math>\mathbb{R}</math>. This means that $f\left(x\right) cannot be expressed as the product of two non-constant polynomials with integer coefficients.
+
In other words, <math>f\left(x\right)</math> cannot be expressed as <math>g\left(x\right)h\left(x\right)</math> for polynomials <math>g\left(x\right)</math> and <math>h\left(x\right)</math> in <math>\mathbb{R}</math>. This means that <math>f\left(x\right)</math> cannot be expressed as the product of two non-constant polynomials with integer coefficients.
  
 
Q.E.D.
 
Q.E.D.

Revision as of 15:39, 28 July 2015

Let $f\left(x\right)=x^n+5x^{n-1}+3$, where $n>1$ is an integer. Prove that $f\left(x\right)$ cannot be expressed as the product of two non-constant polynomials with integer coefficients.

Solution

For the sake of contradiction, assume that $f\left(x\right)=g\left(x\right)h\left(x\right)$ for polynomials $g\left(x\right)$ and $h\left(x\right)$ in $\mathbb{R}$. Furthermore, let $g\left(x\right)=b_mx^m+b_{m-1}x^{m-1}+\ldots+b_1x+b_0$ with $b_i=0$ if $i>m$ and $h\left(x\right)=c_{n-m}x^{n-m}+c_{n-m-1}x^{n-m-1}+\ldots+c_1x+c_0$ with $c_i=0$ if $i>n-m$. This gives that $f\left(x\right)=\sum_{i=0}^{n}\left(\sum_{j=0}^{i}b_jc_{i-j}\right)x^i$.

We have that $3=b_0c_0$, or $3|b_0c_0$. WLOG, let $3|b_0$ (and thus $3\not|c_0$). Since $b_0c_1+b_1c_0=0$ and $3$ divides $b_0$ but not $c_0$, we need that $3|b_1$. We can keep on going up the chain until we get that $3|b_{n-2}$. Then, by equating coefficients once more, we get that $b_0c_{n-1}+b_1c_{n-2}+\ldots+b_{n-2}c_1+b_{n-1}c_0=5$. Taking the equation $\pmod5$ gives that $b_{n-1}c_0\equiv2\pmod5$. This implies that $b_{n-1}\neq0$. Thus, the degree of $g\left(x\right)$ is at least $n-1$. However, because $g\left(x\right)$ is a non-constant factor of $f\left(x\right)$, we have that the degree of $g\left(x\right)$ is at most $n-1$. Thus, the degree of $g\left(x\right)$ \textit{is} $n-1$, implying that the degree of $h\left(x\right)$ is $1$.

From this fact, we have that there must exist a rational root of $f\left(x\right)$. The only candidates are $1$, $-1$, $3$, and $-3$, though. $f\left(1\right)=9\neq0$, $f\left(-1\right)=\pm4+3\neq0$, $f\left(3\right)=3^n+5\cdot3^{n-1}+3>0$, and $f\left(-3\right)=\pm\left(2\cdot3^n\right)+3\neq0$, so none of these work. Thus, there are no linear factors of $f\left(x\right)$.

In other words, $f\left(x\right)$ cannot be expressed as $g\left(x\right)h\left(x\right)$ for polynomials $g\left(x\right)$ and $h\left(x\right)$ in $\mathbb{R}$. This means that $f\left(x\right)$ cannot be expressed as the product of two non-constant polynomials with integer coefficients.

Q.E.D.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1993_IMO_Problems/Problem_1&oldid=71376"