Difference between revisions of "2008 USAMO Problems/Problem 1"
5849206328x (talk | contribs) m |
m (→Solution 6) |
||
(3 intermediate revisions by 3 users not shown) | |||
Line 64: | Line 64: | ||
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>. | ||
+ | === 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\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''' | ||
+ | |||
+ | == Solution 6 == | ||
+ | Very similar to some above solutions. | ||
+ | |||
+ | Let <math>k_{0}k_{1}\dots k_{n}-1=a(a+1)</math>. We wish to show this equation has a solution <math>(a,k_{0},\dots,k_{n})\in\mathbb{Z}^{n+2}</math> for any <math>n\in\mathbb{N}</math>. If <math>a^{2}+a+1</math> has at least <math>n+1</math> distinct prime factors, we can set <math>a^{2}+a+1=p_{1}^{q_{1}}p_{2}^{q_{2}}\dots p_{m}^{q_{m}}</math> for some <math>m\geq n</math> where <math>p_{1},\dots p_{m}</math> are distinct primes. Then, we let <math>k_{i}=p_{i+1}^{q_{i+1}}</math> for all <math>0\leq i\leq n-1</math> and set <math>k_{n}=p_{n+1}^{q_{n+1}}\dots p_{m}^{q_{m}}</math>. Thus, it remains to show <math>a^{2}+a+1</math> can have at least <math>n+1</math> distinct prime factors. We will do this by showing it can have arbitrarily many. | ||
+ | |||
+ | Using an induction-type argument (it isn't exactly induction though), we first show that <math>a^{2}+a+1</math> can have <math>1</math> prime factor by setting <math>a=2</math>. Now, assume <math>a^{2}+a+1</math> has <math>n</math> distinct prime factors. We wish to show there exists some <math>b</math> such that <math>b^{2}+b+1</math> has more than <math>n</math> distinct prime factors (we need not show it has <math>n+1</math>, since we only wish to demonstrate that the number of prime factors can be arbitrarily large rather than any integer). Set <math>b=a^{2}</math>. Then | ||
+ | <cmath>\begin{align*} | ||
+ | b^{2}+b+1&=(b+1)^{2}-b\\ | ||
+ | &=(a^{2}+1)^{2}-a^{2}\\ | ||
+ | &=(a^{2}+a+1)(a^{2}-a+1). | ||
+ | \end{align*}</cmath> | ||
+ | Suppose <math>p</math> is a positive integer dividing both <math>a^{2}+a+1</math> and <math>a^{2}-a+1</math>. Then <math>p\mid(a^{2}+a+1)-(a^{2}-a+1)=2a</math>, and because <math>(a^{2}+a+1)</math> is always odd, we have <math>2\nmid p</math> so <math>p\mid a</math>. But this yields <math>p\mid\gcd(a,a^{2}+a+1)=1</math>, so <math>p=1</math> and thus <math>a^{2}+a+1</math> and <math>a^{2}-a+1</math> are coprime. Therefore, as one can make <math>a^{2}-a+1>1</math>, we see that <math>a^{2}-a+1</math> has at least one prime factor which does not divide <math>a^{2}+a+1</math> (which has <math>n</math> distinct prime factors). Therefore, <math>b^{2}+b+1</math> has more than <math>n</math> distinct prime factors. | ||
{{alternate solutions}} | {{alternate solutions}} |
Latest revision as of 03:38, 17 August 2019
Contents
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
.
Solution 4
Write the relation to be proved as
There are infinitely many primes for which
is a quadratic residue. Let
be such primes. Using the Chinese Remainder Theorem to specify
modulo
, we can find an integer
such that
for some positive integer
. Grouping the factors of
appropriately with the
's, we obtain
with
pairwise relatively prime. We then have
, as desired.
Solution 5
We are supposed to show that for every positive integer , there is a positive integer
such that
has at least
distinct prime divisors. We can actually prove a more general statement.
Claim. Let be a polynomial of degree
with integer coefficients. Then for every positive integer
, there is a positive integer
such that
has at least
distinct prime divisors.
The proof follows from the following two lemmas.
Lemma 1. The set
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 in
, then for each integer
,
is an integer with no prime factors, which must equal
or
. However, since
has degree
, it takes each of the values
and
at most
times, a contradiction.
End Lemma
Lemma 2. Let ,
be primes in
. Then there is a positive integer
such that
is divisible by
.
Proof. For , since
we can find an integer
such that
is divisible by
whenever
. By the Chinese Remainder Theorem, the system of
congruences
,
has positive integer solutions. For every positive integer
that solves this system,
is divisible by
.
End Lemma
Solution 6
Very similar to some above solutions.
Let . We wish to show this equation has a solution
for any
. If
has at least
distinct prime factors, we can set
for some
where
are distinct primes. Then, we let
for all
and set
. Thus, it remains to show
can have at least
distinct prime factors. We will do this by showing it can have arbitrarily many.
Using an induction-type argument (it isn't exactly induction though), we first show that can have
prime factor by setting
. Now, assume
has
distinct prime factors. We wish to show there exists some
such that
has more than
distinct prime factors (we need not show it has
, since we only wish to demonstrate that the number of prime factors can be arbitrarily large rather than any integer). Set
. Then
Suppose
is a positive integer dividing both
and
. Then
, and because
is always odd, we have
so
. But this yields
, so
and thus
and
are coprime. Therefore, as one can make
, we see that
has at least one prime factor which does not divide
(which has
distinct prime factors). Therefore,
has more than
distinct prime factors.
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.