2008 USAMO Problems/Problem 1

From AoPSWiki

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$