Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2008 USAMO Problems/Problem 1"

(problem and solution)
 
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 $n$, there are pairwise relatively prime integers $k_0, k_1 \dotsc, k_n$, all strictly greater than 1, such that $k_0 k_1 \dotsm k_n -1$ is the product of two consecutive integers.

Solutions

Solution 1

We will prove the problem for each nonnegative integer $n$. We wish to show that \[k_0 k_1 \dotsc k_n = a^2+a+1,\] for some integer $a$. We induct on $n$. For our base case, $n=0$, we may let $a$ be positive integer.

For the inductive step, suppose that $k_0, \dotsc, k_{n-1}$ are pairwise relatively prime integers such that \[k_0 \dotsm k_{n-1} = a^2+a+1,\] for some integer $a$. Let $k_n = a^2 + 3a+3$. Evidently, $k_n >1$. Also, \[\gcd(a^2+a+1, k_n) = \gcd\bigl(a^2+a+1, k_n - (a^2+a+1) \bigr) = \gcd\bigl(a^2 + a+1, 2(a+1) \bigr) .\] Since $a^2+a+1 = a(a+1)+1$ is odd and relatively prime to $a+1$, it follows that $a^2+a+1$ and $k_n$ are relatively prime, so $k_n$ is relatively prime to each of $k_0, \dotsc, k_{n-1}$. Finally, \begin{align*} k_0 k_1 \dotsm k_n &= (a^2+a+1)(a^2+3a+3)\\ &= \bigl[ (a+1)^2-a \bigr] \cdot \bigl[ (a+1)^2 + a+2 \bigr] \\ &= (a+1)^4 + 2(a+1)^2 - a^2-2a \\ &= (a+1)^4 + (a+1)^2 + 1 . \end{align*} This completes the induction. $\blacksquare$

Solution 2

Lemma. If $p$ is prime such that $p\equiv 1 \pmod{3}$, there exists a residue $r$ such that $p \mid r^2+r+1$.

Proof. Let $g$ be a multiplicative generator of the nonzero integers mod 3. Set $r \equiv g^{(p-1)/3}$. Then $r-1 \not\equiv 0 \pmod{p}$, but $r^3-1 \equiv 0 \pmod{p}$, so $\frac{r^3-1}{r-1} \equiv r^2 + r+1 \equiv 0 \pmod{p}$. $\blacksquare$

By Dirichlet's Theorem, there are infinitely many primes congruent to 1 (mod 3). Let $p_0, \dotsc, p_n$ be $(n+1)$ such primes, and let $r_0, \dotsc, r_n$ be respective residues as described in the lemma. By the Chinese Remainder Theorem, there is a positive integer $a$ that satisfies the relation \[a \equiv r_i \pmod{p_i}\] for each integer $i \in [0,n]$. Then \[p_0 \dotsc p_n \mid a^2+a+1 .\] Now, for $1 \le i \le n$, take $k_i$ to be the greatest power of $p_i$ that divides $a^2 + a +1$, and let $k_0 = (a^2+a+1)/(k_1 \dotsm k_n)$. Since all the $k_i$ are pairwise relatively prime and are greater than 1, we are done. $\blacksquare$

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>
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2008_USAMO_Problems/Problem_1&oldid=25776"