Difference between revisions of "2008 USAMO Problems/Problem 1"
5849206328x (talk | contribs) m (→Resources) |
5849206328x (talk | contribs) m |
||
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. | ||
− | |||
== 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 | ||
Line 27: | Line 26: | ||
''Proof.'' Let <math>g</math> be a multiplicative generator of the nonzero integers mod p. Set <math>r \equiv g^{(p-1)/3}</math>. Then <math>r-1 \not\equiv 0 \pmod{p}</math>, but <math>r^3-1 \equiv 0 \pmod{p}</math>, so <math>\frac{r^3-1}{r-1} \equiv r^2 + r+1 \equiv 0 \pmod{p}</math>. | ''Proof.'' Let <math>g</math> be a multiplicative generator of the nonzero integers mod p. Set <math>r \equiv g^{(p-1)/3}</math>. Then <math>r-1 \not\equiv 0 \pmod{p}</math>, but <math>r^3-1 \equiv 0 \pmod{p}</math>, so <math>\frac{r^3-1}{r-1} \equiv r^2 + r+1 \equiv 0 \pmod{p}</math>. | ||
+ | |||
+ | '''End Lemma''' | ||
By [[Dirichlet's Theorem]], there are infinitely many primes congruent to 1 (mod 3). Let <math>p_0, \dotsc, p_n</math> be <math>(n+1)</math> such primes, and let <math>r_0, \dotsc, r_n</math> be respective residues as described in the lemma. By the [[Chinese Remainder Theorem]], there is a positive integer <math>a</math> that satisfies the relation | By [[Dirichlet's Theorem]], there are infinitely many primes congruent to 1 (mod 3). Let <math>p_0, \dotsc, p_n</math> be <math>(n+1)</math> such primes, and let <math>r_0, \dotsc, r_n</math> be respective residues as described in the lemma. By the [[Chinese Remainder Theorem]], there is a positive integer <math>a</math> that satisfies the relation | ||
Line 40: | Line 41: | ||
Define <math>P</math> to be the greatest possible cardinality of a relatively prime partition for that number. | Define <math>P</math> to be the greatest possible cardinality of a relatively prime partition for that number. | ||
− | Lemma 1 | + | '''Lemma 1.''' All cardinalities of the relatively prime partitions of a number up to <math>P</math> can be attained. |
− | Proof | + | ''Proof.'' <math>P = P - 0</math> satisfies the properties. For any <math>P - n</math> which satisfies the properties, we can take any of the 2 <math>P - n</math> 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 <math>P - n - 1</math> numbers which satisfy the conditions, unless <math>P - n = 1</math>, because there is only one number left. Therefore, all numbers of numbers of relatively prime factors from <math>1</math> to <math>P - 1</math> are attainable, if <math>P</math> is attainable as well. |
− | <math>P = P - 0</math> satisfies the properties. For any <math>P - n</math> which satisfies the properties, we can take any of the 2 <math>P - n</math> 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 <math>P - n - 1</math> numbers which satisfy the conditions, unless <math>P - n = 1</math>, because there is only one number left. Therefore, all numbers of numbers of relatively prime factors from <math>1</math> to <math>P - 1</math> are attainable, if <math>P</math> is attainable as well. | ||
− | End Lemma | + | '''End Lemma''' |
− | Lemma 2 | + | '''Lemma 2.''' <math>a^2 + a + 1</math> can have arbitrarily many prime factors for some value of <math>a</math>. |
− | Proof | + | ''Proof.'' Let <math>f(x) = x^2 + x + 1</math>. Let <math>a^2 + a + 1 = k</math>. Then <math>f(a + k) = a^2 + 2ak + k^2 + a + k + 1 = 2ak + k^2 + 2k</math>. |
− | Let <math>f(x) = x^2 + x + 1</math>. Let <math>a^2 + a + 1 = k</math>. Then <math>f(a + k) = a^2 + 2ak + k^2 + a + k + 1 = 2ak + k^2 + 2k</math>. | ||
After factoring, we get <math>k(k + 2 + 2a) = (a^2 + a + 1)(a^2 + 3a + 3)</math>. | After factoring, we get <math>k(k + 2 + 2a) = (a^2 + a + 1)(a^2 + 3a + 3)</math>. | ||
<math>a^2 + 3a + 3 \geq a^2 + a + 1</math>, because <math>a</math> is strictly positive. | <math>a^2 + 3a + 3 \geq a^2 + a + 1</math>, because <math>a</math> is strictly positive. | ||
Line 60: | Line 59: | ||
<math>(a^2 + a + 1)(a^2 + 3a + 3)</math> therefore must contain prime factors not in <math>a^2 + a + 1</math>. Upon repeating this an arbitrary number of times, we get a number of the form <math>a^2 + a + 1</math> which has arbitrarily many distinct prime factors. | <math>(a^2 + a + 1)(a^2 + 3a + 3)</math> therefore must contain prime factors not in <math>a^2 + a + 1</math>. Upon repeating this an arbitrary number of times, we get a number of the form <math>a^2 + a + 1</math> which has arbitrarily many distinct prime factors. | ||
− | End Lemma | + | '''End Lemma''' |
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. | 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>. | 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>. | ||
+ | |||
+ | |||
{{alternate solutions}} | {{alternate solutions}} | ||
== See also == | == See also == | ||
+ | * <url>viewtopic.php?t=202909 Discussion on AoPS/MathLinks</url> | ||
{{USAMO newbox|year=2008|before=First Question|num-a=2}} | {{USAMO newbox|year=2008|before=First Question|num-a=2}} |
Revision as of 21:59, 12 August 2014
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.
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 p. Set . Then , but , so .
End Lemma
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.
Solution 3
Firstly, we see that there are numbers . Since , there are at least 2 values of . Define a relatively prime partition to be a set of relatively prime numbers such that their product is equal to some natural number.
Define 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 can be attained.
Proof. satisfies the properties. For any which satisfies the properties, we can take any of the 2 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 numbers which satisfy the conditions, unless , because there is only one number left. Therefore, all numbers of numbers of relatively prime factors from to are attainable, if is attainable as well.
End Lemma
Lemma 2. can have arbitrarily many prime factors for some value of .
Proof. Let . Let . Then . After factoring, we get . , because is strictly positive. Let their GCD=g. , and so , but which is strictly odd, so g=1. therefore must contain prime factors not in . Upon repeating this an arbitrary number of times, we get a number of the form which has arbitrarily many distinct prime factors.
End Lemma
Then would not have elements in the relatively prime partition for some value of n, and any value of a. It is possible to choose a value of such that has arbitrarily many unique prime factors, by our second Lemma, and so it is possible for 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 , is the product of 2 consecutive integers, we see that the given statement is true because if , then .
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
See also
- <url>viewtopic.php?t=202909 Discussion on AoPS/MathLinks</url>
2008 USAMO (Problems • Resources) | ||
Preceded by First Question |
Followed by Problem 2 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.