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

Revision as of 22:50, 12 August 2014

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.

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 p. 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}$ .

End Lemma

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.

Solution 3

Firstly, we see that there are $n + 1$ numbers $k_i$ . Since $n\geq1$ , there are at least 2 values of $k_i$ . Define a relatively prime partition to be a set of relatively prime numbers such that their product is equal to some natural number.

Define $P$ to be the greatest possible cardinality of a relatively prime partition for that number.

Lemma 1. All cardinalities of the relatively prime partitions of a number up to $P$ can be attained.

Proof. $P = P - 0$ satisfies the properties. For any $P - n$ which satisfies the properties, we can take any of the 2 $P - n$ numbers and multiply them together. Because they are both relatively prime to all the other numbers, their product is relatively prime to all the other numbers as well, and that results in $P - n - 1$ numbers which satisfy the conditions, unless $P - n = 1$ , because there is only one number left. Therefore, all numbers of numbers of relatively prime factors from $1$ to $P - 1$ are attainable, if $P$ is attainable as well.

End Lemma

Lemma 2. $a^2 + a + 1$ can have arbitrarily many prime factors for some value of $a$ .

Proof. Let $f(x) = x^2 + x + 1$ . Let $a^2 + a + 1 = k$ . Then $f(a + k) = a^2 + 2ak + k^2 + a + k + 1 = 2ak + k^2 + 2k$ . After factoring, we get $k(k + 2 + 2a) = (a^2 + a + 1)(a^2 + 3a + 3)$ . $a^2 + 3a + 3 \geq a^2 + a + 1$ , because $a$ is strictly positive. Let their GCD=g. $g|2a + 2$ $g|2a^2 + 2a$ $g|a^2 - 3a - 3 + a^2 + 3a + 3, g|2a^2$ $g|2a$ , and so $g|2$ , but $g|a^2 + a + 3$ which is strictly odd, so g=1. $(a^2 + a + 1)(a^2 + 3a + 3)$ therefore must contain prime factors not in $a^2 + a + 1$ . Upon repeating this an arbitrary number of times, we get a number of the form $a^2 + a + 1$ which has arbitrarily many distinct prime factors.

End Lemma

Then $a(a + 1) + 1 = a^2 + a + 1$ would not have $n + 1 = P$ elements in the relatively prime partition for some value of n, and any value of a. It is possible to choose a value of $a$ such that $a^2 + a + 1$ has arbitrarily many unique prime factors, by our second Lemma, and so it is possible for $P$ to be arbitrarily high. By our first Lemma, all numbers up to P are possible values for the cardinality of some relatively prime partition, and so there always exists some number that has an arbitrary number of elements in a relatively prime partition. Because $a^2 + a + 1 = a(a + 1) + 1$ , $a(a + 1)$ is the product of 2 consecutive integers, we see that the given statement is true because if $k_0k_1...k_n = a(a + 1) + 1$ , then $k_0k_1...k_n - 1 = a(a + 1)$ .

Solution 4

Write the relation to be proved as $4k_0k_1\cdots k_n = 4a(a + 1) + 4 = (2a + 1)^2 + 3.$ There are infinitely many primes for which $-3$ is a quadratic residue. Let $2 < p_0 < p_1 < \cdots < p_n$ be such primes. Using the Chinese Remainder Theorem to specify $a$ modulo $p_n$ , we can find an integer $a$ such that $(2a + 1)^2 + 3 = 4p_0p_1\cdots p_nm$ for some positive integer $m$ . Grouping the factors of $m$ appropriately with the $p_i$ 's, we obtain $(2a + 1)^2 + 3 = 4k_0k_1\cdots k_n$ with $k_i$ pairwise relatively prime. We then have $k_0k_1\cdots k_n - 1 = a(a + 1)$ , as desired.

Solution 5

We are supposed to show that for every positive integer $n$ , there is a positive integer $x$ such that $x(x + 1) + 1 = x^2 + x + 1$ has at least $n$ distinct prime divisors. We can actually prove a more general statement.

Claim. Let $P(x) = a_dx^d + \cdots + a_1x + 1$ be a polynomial of degree $d\geq 1$ with integer coefficients. Then for every positive integer $n$ , there is a positive integer $x$ such that $P(x)$ has at least $n$ distinct prime divisors.

The proof follows from the following two lemmas.

Lemma 1. The set

\[Q = \{p\mid p\text{ a prime for which there is an integer }x\m\text{ such that }p\text{ divides }P(x)\}\] (Error compiling LaTeX. Unknown error_msg)

is infinite.

Proof. The proof is analogous to Euclid's proof that there are infinitely many primes. Namely, if we assume that there are only finitely many primes $p_1, p_2, \ldots, p_k$ in $Q$ , then for each integer $m$ , $P(mp_1p_2\cdots p_k)$ is an integer with no prime factors, which must equal $1$ or $-1$ . However, since $P$ has degree $d\geq 1$ , it takes each of the values $1$ and $-1$ at most $d$ times, a contradiction.

End Lemma

Lemma 2. Let $p_1, p_2, \ldots, p_n$ , $n\geq 1$ be primes in $Q$ . Then there is a positive integer $x$ such that $P(x)$ is divisible by $p_1p_2\cdots p_n$ .

Proof. For $i = 1, 2, \ldots, n$ , since $p_i\in Q$ we can find an integer $c_i$ such that $P(x)$ is divisible by $p_i$ whenever $x\equiv c_i\pmod{p_i}$ . By the Chinese Remainder Theorem, the system of $n$ congruences $x\equiv c_i\pmod{p_i}$ , $i = 1, 2, \ldots, n$ has positive integer solutions. For every positive integer $x$ that solves this system, $P(x)$ is divisible by $p_1p_2\cdots p_n$ .

End Lemma

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

@@ Line 63: / Line 63: @@
 Then <math>a(a + 1) + 1 = a^2 + a + 1</math> would not have <math>n + 1 = P</math> elements in the relatively prime partition for some value of n, and any value of a.
 It is possible to choose a value of <math>a</math> such that <math>a^2 + a + 1</math> has arbitrarily many unique prime factors, by our second Lemma, and so it is possible for <math>P</math> to be arbitrarily high. By our first Lemma, all numbers up to P are possible values for the cardinality of some relatively prime partition, and so there always exists some number that has an arbitrary number of elements in a relatively prime partition. Because <math>a^2 + a + 1 = a(a + 1) + 1</math>, <math>a(a + 1)</math> is the product of 2 consecutive integers, we see that the given statement is true because if <math>k_0k_1...k_n = a(a + 1) + 1</math>, then <math>k_0k_1...k_n - 1 = a(a + 1)</math>.
+=== Solution 4 ===
+Write the relation to be proved as
+<cmath>4k_0k_1\cdots k_n = 4a(a + 1) + 4 = (2a + 1)^2 + 3.</cmath>
+There are infinitely many primes for which <math>-3</math> is a quadratic residue. Let <math>2 < p_0 < p_1 < \cdots < p_n</math> be such primes. Using the Chinese Remainder Theorem to specify <math>a</math> modulo <math>p_n</math>, we can find an integer <math>a</math> such that <math>(2a + 1)^2 + 3 = 4p_0p_1\cdots p_nm</math> for some positive integer <math>m</math>. Grouping the factors of <math>m</math> appropriately with the <math>p_i</math>'s, we obtain <math>(2a + 1)^2 + 3 = 4k_0k_1\cdots k_n</math> with <math>k_i</math> pairwise relatively prime. We then have <math>k_0k_1\cdots k_n - 1 = a(a + 1)</math>, as desired.
+=== Solution 5 ===
+We are supposed to show that for every positive integer <math>n</math>, there is a positive integer <math>x</math> such that <math>x(x + 1) + 1 = x^2 + x + 1</math> has at least <math>n</math> distinct prime divisors. We can actually prove a more general statement.
+'''Claim.''' Let <math>P(x) = a_dx^d + \cdots + a_1x + 1</math> be a polynomial of degree <math>d\geq 1</math> with integer coefficients. Then for every positive integer <math>n</math>, there is a positive integer <math>x</math> such that <math>P(x)</math> has at least <math>n</math> distinct prime divisors.
+The proof follows from the following two lemmas.
+'''Lemma 1.''' The set
+<cmath>Q = \{p\mid p\text{ a prime for which there is an integer }x\m\text{ such that }p\text{ divides }P(x)\}</cmath>
+is infinite.
+''Proof.'' The proof is analogous to Euclid's proof that there are infinitely many primes. Namely, if we assume that there are only finitely many primes <math>p_1, p_2, \ldots, p_k</math> in <math>Q</math>, then for each integer <math>m</math>, <math>P(mp_1p_2\cdots p_k)</math> is an integer with no prime factors, which must equal <math>1</math> or <math>-1</math>. However, since <math>P</math> has degree <math>d\geq 1</math>, it takes each of the values <math>1</math> and <math>-1</math> at most <math>d</math> times, a contradiction.
+'''End Lemma'''
+'''Lemma 2.''' Let <math>p_1, p_2, \ldots, p_n</math>, <math>n\geq 1</math> be primes in <math>Q</math>. Then there is a positive integer <math>x</math> such that <math>P(x)</math> is divisible by <math>p_1p_2\cdots p_n</math>.
+''Proof.'' For <math>i = 1, 2, \ldots, n</math>, since <math>p_i\in Q</math> we can find an integer <math>c_i</math> such that <math>P(x)</math> is divisible by <math>p_i</math> whenever <math>x\equiv c_i\pmod{p_i}</math>. By the Chinese Remainder Theorem, the system of <math>n</math> congruences <math>x\equiv c_i\pmod{p_i}</math>, <math>i = 1, 2, \ldots, n</math> has positive integer solutions. For every positive integer <math>x</math> that solves this system, <math>P(x)</math> is divisible by <math>p_1p_2\cdots p_n</math>.
+'''End Lemma'''

2008 USAMO (Problems • Resources)
Preceded by First Question	Followed by Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search

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

Revision as of 22:50, 12 August 2014

Contents

Problem

Solutions

Solution 1

Solution 2

Solution 3

Solution 4

Solution 5

See also