Difference between revisions of "2008 USAMO Problems/Problem 1"
I like pie (talk | contribs) m (Moved TOC + minor edits) |
I like pie (talk | contribs) (Fixed link) |
||
Line 39: | Line 39: | ||
{{USAMO newbox|year=2008|beforetext=|before=First Problem|num-a=2}} | {{USAMO newbox|year=2008|beforetext=|before=First Problem|num-a=2}} | ||
− | * <url> | + | * <url>viewtopic.php?t=202909 Discussion on AoPS/MathLinks</url> |
[[Category:Olympiad Number Theory Problems]] | [[Category:Olympiad Number Theory Problems]] |
Revision as of 18:57, 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>viewtopic.php?t=202909 Discussion on AoPS/MathLinks</url>