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"
(→‎Solution 2)
 
(13 intermediate revisions by 7 users not shown)
Line 1: Line 1:
 +
==Problem==
 +
 
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-constant polynomials with integer coefficients.
 
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-constant polynomials with integer coefficients.
  
Line 5: Line 7:
 
For the sake of contradiction, assume that <math>f\left(x\right)=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>. Furthermore, let <math>g\left(x\right)=b_mx^m+b_{m-1}x^{m-1}+\ldots+b_1x+b_0</math> with <math>b_i=0</math> if <math>i>m</math> and <math>h\left(x\right)=c_{n-m}x^{n-m}+c_{n-m-1}x^{n-m-1}+\ldots+c_1x+c_0</math> with <math>c_i=0</math> if <math>i>n-m</math>. This gives that <math>f\left(x\right)=\sum_{i=0}^{n}\left(\sum_{j=0}^{i}b_jc_{i-j}\right)x^i</math>.
 
For the sake of contradiction, assume that <math>f\left(x\right)=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>. Furthermore, let <math>g\left(x\right)=b_mx^m+b_{m-1}x^{m-1}+\ldots+b_1x+b_0</math> with <math>b_i=0</math> if <math>i>m</math> and <math>h\left(x\right)=c_{n-m}x^{n-m}+c_{n-m-1}x^{n-m-1}+\ldots+c_1x+c_0</math> with <math>c_i=0</math> if <math>i>n-m</math>. This gives that <math>f\left(x\right)=\sum_{i=0}^{n}\left(\sum_{j=0}^{i}b_jc_{i-j}\right)x^i</math>.
  
−
We have that <math>3=b_0c_0</math>, or <math>3|b_0c_0</math>. WLOG, let <math>3|b_0</math> (and thus <math>3\not|c_0</math>). Since <math>b_0c_1+b_1c_0=0</math> and <math>3</math> divides <math>b_0</math> but not <math>c_0</math>, we need that <math>3|b_1</math>. We can keep on going up the chain until we get that <math>3|b_{n-2}</math>. Then, by equating coefficients once more, we get that <math>b_0c_{n-1}+b_1c_{n-2}+\ldots+b_{n-2}c_1+b_{n-1}c_0=5</math>. Taking the equation <math>\pmod5</math> gives that <math>b_{n-1}c_0\equiv2\pmod5</math>. This implies that <math>b_{n-1}\neq0</math>. Thus, the degree of <math>g\left(x\right)</math> is at least <math>n-1</math>. However, because <math>g\left(x\right)</math> is a non-constant factor of <math>f\left(x\right)</math>, we have that the degree of <math>g\left(x\right)</math> is at most <math>n-1</math>. Thus, the degree of <math>g\left(x\right)</math> is <math>n-1</math>, implying that the degree of <math>h\left(x\right)</math> is <math>1</math>.
+
We have that <math>3=b_0c_0</math>, or <math>3|b_0c_0</math>. WLOG, let <math>3|b_0</math> (and thus <math>3\not|c_0</math>). Since <math>b_0c_1+b_1c_0=0</math> and <math>3</math> divides <math>b_0</math> but not <math>c_0</math>, we need that <math>3|b_1</math>. We can keep on going up the chain until we get that <math>3|b_{n-2}</math>. Then, by equating coefficients once more, we get that <math>b_0c_{n-1}+b_1c_{n-2}+\ldots+b_{n-2}c_1+b_{n-1}c_0=5</math>. Taking the equation <math>\pmod3</math> gives that <math>b_{n-1}c_0\equiv2\pmod3</math>. This implies that <math>b_{n-1}\neq0</math>. Thus, the degree of <math>g\left(x\right)</math> is at least <math>n-1</math>. However, because <math>h\left(x\right)</math> is a non-constant factor of <math>f\left(x\right)</math>, we have that the degree of <math>g\left(x\right)</math> is at most <math>n-1</math>. Thus, the degree of <math>g\left(x\right)</math> is <math>n-1</math>, implying that the degree of <math>h\left(x\right)</math> is <math>1</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>.
+
From this fact, we have that there must exist an integer root of <math>f\left(x\right)</math>. However, when <math>x</math> is an integer, <math>x^n + 5x^{n - 1} \equiv x^{n - 2}x(x + 1) \equiv 0 \pmod{2}</math>, meaning <math>f(x)</math> is odd, so <math>x</math> cannot be a root of <math>f</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 <math>f\left(x\right)</math> cannot be expressed as the product of two non-constant polynomials with integer coefficients.
+
Hence, <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.
  
−
== Alternate Solution ==
+
== Solution 2 ==
 +
Let us assume the contrary. If <math>f(x)=p(x)q(x)</math>, then that is equivalent to <math>x^{n-1}(x+5)=p(x)q(x)-3</math>. Now we see that <math>p(0)q(0)=3</math> and <math>p(-5)q(-5)=3</math>. This implies that the constant terms of <math>p</math> and <math>q</math> are either <math>-1,-3</math> or <math>1,3</math>, up to permutation. Let <math>p(x)=a(x)+3</math> and <math>q(x)=b(x)+1</math>. The only possibility for <math>p(-5)q(-5)</math> to be equal to <math>3</math> is to make <math>a(-5)=b(-5)=0</math>. This is because if they are not zero they must be nonzero multiples of 5, and so <math>p(-5)q(-5)</math> must be larger than 3. So <math>p(x)-3=(x+5)A(x)</math> and <math>q(x)-1=(x+5)B(x)</math>. Now plug these back to  <math>x^{n-1}(x+5)=p(x)q(x)-3</math> we see that <cmath>x^{n-1}(x+5)=[(x+5)A(x)+3][(x+5)B(x)+1]-3</cmath>. This is equivalent to <cmath>(x+5)^2A(x)B(x)+(x+5)A(x)+3(x+5)B(x)=(x+5)x^{n-1}</cmath>. One of <math>A(x)</math> and <math>B(x)</math> must be 0. But then that implies one of <math>p</math> and <math>q</math> is less than degree 1. So the assumption must be false. The <math>(-1,-3)</math> case is similar.
 +
 
 +
-by CreamyCream 123
 +
 
 +
==Alternate Solution==
 +
 
 +
It’s actually trivial by Perron’s Criterion lol
 +
 
 +
 
 +
Note: Quoting Perron's Criterion on the actual IMO will very likely result in a score in the set <math>\{0,1\}</math>, since it was not a well-known result back then.
 +
 
 +
==See Also==
  
−
Trivial by Perron's Criterion lol
+
{{IMO box|year=1993|before=First Question|num-a=2}}

Latest revision as of 22:24, 28 September 2025

Problem

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 $\pmod3$ gives that $b_{n-1}c_0\equiv2\pmod3$. This implies that $b_{n-1}\neq0$. Thus, the degree of $g\left(x\right)$ is at least $n-1$. However, because $h\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)$ is $n-1$, implying that the degree of $h\left(x\right)$ is $1$.

From this fact, we have that there must exist an integer root of $f\left(x\right)$. However, when $x$ is an integer, $x^n + 5x^{n - 1} \equiv x^{n - 2}x(x + 1) \equiv 0 \pmod{2}$, meaning $f(x)$ is odd, so $x$ cannot be a root of $f$.

Hence, $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.

Solution 2

Let us assume the contrary. If $f(x)=p(x)q(x)$, then that is equivalent to $x^{n-1}(x+5)=p(x)q(x)-3$. Now we see that $p(0)q(0)=3$ and $p(-5)q(-5)=3$. This implies that the constant terms of $p$ and $q$ are either $-1,-3$ or $1,3$, up to permutation. Let $p(x)=a(x)+3$ and $q(x)=b(x)+1$. The only possibility for $p(-5)q(-5)$ to be equal to $3$ is to make $a(-5)=b(-5)=0$. This is because if they are not zero they must be nonzero multiples of 5, and so $p(-5)q(-5)$ must be larger than 3. So $p(x)-3=(x+5)A(x)$ and $q(x)-1=(x+5)B(x)$. Now plug these back to $x^{n-1}(x+5)=p(x)q(x)-3$ we see that \[x^{n-1}(x+5)=[(x+5)A(x)+3][(x+5)B(x)+1]-3\]. This is equivalent to \[(x+5)^2A(x)B(x)+(x+5)A(x)+3(x+5)B(x)=(x+5)x^{n-1}\]. One of $A(x)$ and $B(x)$ must be 0. But then that implies one of $p$ and $q$ is less than degree 1. So the assumption must be false. The $(-1,-3)$ case is similar.

-by CreamyCream 123

Alternate Solution

It’s actually trivial by Perron’s Criterion lol


Note: Quoting Perron's Criterion on the actual IMO will very likely result in a score in the set $\{0,1\}$, since it was not a well-known result back then.

See Also

1993 IMO (Problems) • Resources
Preceded by
First Question 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 2
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1993_IMO_Problems/Problem_1&oldid=261783"