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

m (Moved TOC + minor edits)
(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>Forum/viewtopic.php?t=202909 Discussion on AoPS/MathLinks</url>
* <url>viewtopic.php?t=202909 Discussion on AoPS/MathLinks</url>
[[Category:Olympiad Number Theory Problems]]
[[Category:Olympiad Number Theory Problems]]

Revision as of 19:57, 1 May 2008


(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.


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.


2008 USAMO (ProblemsResources)
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>
Invalid username
Login to AoPS