Difference between revisions of "2006 USAMO Problems/Problem 4"
(→Solution) |
(making it shorter) |
||
Line 4: | Line 4: | ||
== Solution == | == Solution == | ||
− | Let polynomial <math>P(x)</math> be such that it's roots are only all of <math>a_1</math> through <math>a_k</math> | + | Let polynomial <math>P(x)</math> be a [[monic polynomial]] such that it's roots are only all of <math>a_1</math> through <math>a_k</math>. Therefore, the sum and product of the roots is n, and the constant term of <math>P(x)</math> is <math>\pm n</math>. From the [[Rational Root Theorem]], all <math>a_i</math> are divisors of n, and integral. We split this into cases: |
Revision as of 12:06, 28 January 2008
Problem
Find all positive integers such that there are
positive rational numbers
satisfying
.
Solution
Let polynomial be a monic polynomial such that it's roots are only all of
through
. Therefore, the sum and product of the roots is n, and the constant term of
is
. From the Rational Root Theorem, all
are divisors of n, and integral. We split this into cases:
Case 1: n is prime
If n is prime, the only divisors of n are 1 and n. We must have an n in so that
, but then
, since
. We have a contradiction, therefore n may not be prime.
Case 2: n is composite
Let two divisors of n(not necessarily distinct) be and
, such that
. We will prove that
:
We subtract from
:
. Now we add 1:
. Since
and
are positive,
and
are nonnegative. Therefore,
.
WLOG, we let and
. If
, we can let the rest of the numbers be ones. Therefore, there are such k when n is composite.
Case 3: n=1
Therefore, k=1, but , so that is impossible.
Therefore, there are such such that
only when n is composite.