Difference between revisions of "2008 USAMO Problems/Problem 1"
(problem and solution) |
I like pie (talk | contribs) m (Moved TOC + minor edits) |
||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | |||
(''Titu Andreescu'') | (''Titu Andreescu'') | ||
Prove that for each positive integer <math>n</math>, there are pairwise relatively prime integers <math>k_0, k_1 \dotsc, k_n</math>, all strictly greater than 1, such that <math>k_0 k_1 \dotsm k_n -1</math> is the product of two consecutive integers. | Prove that for each positive integer <math>n</math>, there are pairwise relatively prime integers <math>k_0, k_1 \dotsc, k_n</math>, all strictly greater than 1, such that <math>k_0 k_1 \dotsm k_n -1</math> is the product of two consecutive integers. | ||
+ | __TOC__ | ||
== Solutions == | == Solutions == | ||
− | |||
=== Solution 1 === | === Solution 1 === | ||
− | |||
We will prove the problem for each nonnegative integer <math>n</math>. We wish to show that | We will prove the problem for each nonnegative integer <math>n</math>. We wish to show that | ||
<cmath> k_0 k_1 \dotsc k_n = a^2+a+1, </cmath> | <cmath> k_0 k_1 \dotsc k_n = a^2+a+1, </cmath> | ||
Line 26: | Line 24: | ||
=== Solution 2 === | === Solution 2 === | ||
− | |||
'''Lemma.''' If <math>p</math> is prime such that <math>p\equiv 1 \pmod{3}</math>, there exists a residue <math>r</math> such that <math>p \mid r^2+r+1</math>. | '''Lemma.''' If <math>p</math> is prime such that <math>p\equiv 1 \pmod{3}</math>, there exists a residue <math>r</math> such that <math>p \mid r^2+r+1</math>. | ||
Line 36: | Line 33: | ||
<cmath> p_0 \dotsc p_n \mid a^2+a+1 . </cmath> | <cmath> p_0 \dotsc p_n \mid a^2+a+1 . </cmath> | ||
Now, for <math>1 \le i \le n</math>, take <math>k_i</math> to be the greatest power of <math>p_i</math> that divides <math>a^2 + a +1</math>, and let <math>k_0 = (a^2+a+1)/(k_1 \dotsm k_n)</math>. Since all the <math>k_i</math> are pairwise relatively prime and are greater than 1, we are done. <math>\blacksquare</math> | Now, for <math>1 \le i \le n</math>, take <math>k_i</math> to be the greatest power of <math>p_i</math> that divides <math>a^2 + a +1</math>, and let <math>k_0 = (a^2+a+1)/(k_1 \dotsm k_n)</math>. Since all the <math>k_i</math> are pairwise relatively prime and are greater than 1, we are done. <math>\blacksquare</math> | ||
− | |||
{{alternate solutions}} | {{alternate solutions}} | ||
== Resources == | == Resources == | ||
− | |||
{{USAMO newbox|year=2008|beforetext=|before=First Problem|num-a=2}} | {{USAMO newbox|year=2008|beforetext=|before=First Problem|num-a=2}} | ||
* <url>Forum/viewtopic.php?t=202909 Discussion on AoPS/MathLinks</url> | * <url>Forum/viewtopic.php?t=202909 Discussion on AoPS/MathLinks</url> | ||
− | |||
[[Category:Olympiad Number Theory Problems]] | [[Category:Olympiad Number Theory Problems]] |
Revision as of 17:26, 1 May 2008
Problem
(Titu Andreescu)
Prove that for each positive integer , there are pairwise relatively prime integers
, all strictly greater than 1, such that
is the product of two consecutive integers.
Contents
[hide]Solutions
Solution 1
We will prove the problem for each nonnegative integer . We wish to show that
for some integer
. We induct on
. For our base case,
, we may let
be positive integer.
For the inductive step, suppose that are pairwise relatively prime integers such that
for some integer
. Let
. Evidently,
. Also,
Since
is odd and relatively prime to
, it follows that
and
are relatively prime, so
is relatively prime to each of
. Finally,
This completes the induction.
Solution 2
Lemma. If is prime such that
, there exists a residue
such that
.
Proof. Let be a multiplicative generator of the nonzero integers mod 3. Set
. Then
, but
, so
.
By Dirichlet's Theorem, there are infinitely many primes congruent to 1 (mod 3). Let be
such primes, and let
be respective residues as described in the lemma. By the Chinese Remainder Theorem, there is a positive integer
that satisfies the relation
for each integer
. Then
Now, for
, take
to be the greatest power of
that divides
, and let
. Since all the
are pairwise relatively prime and are greater than 1, we are done.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
Resources
2008 USAMO (Problems • Resources) | ||
First Problem | Followed by Problem 2 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
- <url>Forum/viewtopic.php?t=202909 Discussion on AoPS/MathLinks</url>