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 18: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.
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>