Difference between revisions of "1993 IMO Problems/Problem 1"
(→Solution) |
(→Solution) |
||
Line 7: | Line 7: | ||
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>. | 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(x)\equiv x+5x+3 | + | 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(x)\equiv x+5x+3\equiv1\pmod3</math> when <math>x</math> is an integer, 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 <math>f\left(x\right)</math> 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. |
Revision as of 17:15, 27 August 2021
Let , where
is an integer. Prove that
cannot be expressed as the product of two non-constant polynomials with integer coefficients.
Solution
For the sake of contradiction, assume that for polynomials
and
in
. Furthermore, let
with
if
and
with
if
. This gives that
.
We have that , or
. WLOG, let
(and thus
). Since
and
divides
but not
, we need that
. We can keep on going up the chain until we get that
. Then, by equating coefficients once more, we get that
. Taking the equation
gives that
. This implies that
. Thus, the degree of
is at least
. However, because
is a non-constant factor of
, we have that the degree of
is at most
. Thus, the degree of
is
, implying that the degree of
is
.
From this fact, we have that there must exist a rational root of . The only candidates are
,
,
, and
, though.
when
is an integer, so none of these work. Thus, there are no linear factors of
.
In other words, cannot be expressed as
for polynomials
and
in
. This means that
cannot be expressed as the product of two non-constant polynomials with integer coefficients.
Q.E.D.
Alternate Solution
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 , since it was not a well-known result back then.