|
1.2. Prime Numbers
223
Solution.
Let us define
A
n
−
1
=
p
1
p
2
· · ·
p
n
−
1
and
a
k
=
k A
n
−
1
−
p
n
for 1
≤
k
≤
p
n
−
1. Observe that these numbers are relatively prime. Indeed, a prime common
divisor of
a
k
1
and
a
k
2
would divide
(
k
1
−
k
2
)
A
n
−
1
, and since gcd
(
a
k
1
,
p
n
)
=
1,
this divisor would be one of
p
1
, . . . ,
p
n
−
1
, which is clearly impossible. Of course,
this implies that
a
k
≥
p
n
+
k
(since
a
k
is relatively prime to
p
1
, . . . ,
p
n
−
1
). Thus
for
k
=
p
n
−
1 we have
A
n
−
A
n
−
1
−
p
n
>
p
p
n
+
n
−
1
, and so
p
1
p
2
· · ·
p
n
>
p
p
n
+
n
−
1
>
p
3
n
−
1
for
n
≥
5. From here we find that for
n
≥
6 we have
p
1
· · ·
p
n
>
p
1
· · ·
p
n
2
2
>
p
2
3
n
2
−
1
>
p
2
n
+
1
. In the last inequality it is neces-
sary to have
n
2
≥
5, that is,
n
≥
10. Let us remark that checking cases shows
that this inequality holds for
n
≥
6. For
n
=
5 one can easily check the inequality.
Problem 1.2.14.
Show that there exists a set A of positive integers with the fol-
lowing property: for any infinite set S of primes, there exist two positive integers
m
∈
A and n
∈
A each of which is a product of k distinct elements of S for some
k
≥
2
.
(35th International Mathematical Olympiad)
Solution.
There are several constructions for such
A
, involving different ideas
about the decomposition of integers.
First example.
Let
p
1
<
p
2
<
· · ·
<
p
n
<
· · ·
be the increasing sequence of all
prime numbers. Define
A
as the set of numbers of the form
p
i
1
p
i
2
· · ·
p
i
k
where
i
1
<
i
2
<
· · ·
<
i
k
and
k
=
p
i
1
. For example, 3
·
5
·
7
∈
A
; 3
·
11
·
13
∈
A
and
5
·
7
·
11
∈
A
; 3
·
5
·
7
·
11
∈
A
.
We will see that
A
satisfies the required condition. Let
S
be an infinite set of
prime numbers, say
q
1
<
q
2
<
· · ·
<
q
n
<
· · ·
. Take
m
=
q
1
q
2
· · ·
q
q
1
and
n
=
q
1
q
2
· · ·
q
q
1
+
1
. Then
m
∈
A
and
n
∈
A
.
Second example.
Define
A
=
5
∞
i
=
1
A
i
, where
A
i
is the set of numbers that
are the product of
i
+
1 distinct primes that are different from
p
i
. For example,
3
·
5
·
7
∈
A
2
, 2
·
3
·
7
·
11
∈
A
3
and 2
·
3
·
7
∈
A
2
, 3
·
5
·
7
·
13
∈
A
3
.
Let
S
be an infinite set of prime numbers, say
q
1
<
q
2
<
· · ·
<
q
n
<
· · ·
.
Suppose that
q
1
=
p
i
1
. If
i
1
>
1, note that
i
1
=
k
. Then
n
=
q
1
q
2
· · ·
q
k
+
1
∈
A
,
because it contains a prime factor
q
1
=
p
i
1
=
p
k
. The number
m
=
q
2
q
3
· · ·
q
k
+
2
contains
k
+
1 factors, all different from
p
k
=
q
1
. Thus
m
∈
A
. If
i
1
=
1, take
k
=
i
2
, and the same construction will answer the question.
Third example.
Let
P
be the set of all positive primes and let
P
1
⊂
P
2
⊂ · · · ⊂
P
n
⊂ · · ·
be a nested sequence of finite distinct subsets of
P
such that
P
=
5
∞
i
=
1
P
i
. Define
A
to be the set of elements of the form
a
=
p
1
p
2
· · ·
p
k
,
where
k
=
i
1
<
i
2
<
· · ·
<
i
k
and
p
1
∈
P
i
1
\
P
i
1
−
1
,
p
2
∈
P
i
2
, . . . ,
p
k
∈
P
i
k
.
224
II Solutions, 1. Divisibility
Let
S
be an infinite set of prime numbers and let
S
i
=
S
∩
P
i
. Since
S
=
5
∞
i
=
1
S
i
, there must be infinitely many indices
i
>
1 such that
S
i
−
1
=
S
i
. Let
i
m
be the
m
th such index. Then since
S
i
m
⊂
S
i
m
+
1
=
S
i
m
+
1
, we see that
S
i
1
⊂
S
i
2
⊂
· · · ⊂
S
i
m
⊂ · · ·
is an infinite nested subsequence of distinct sets.
Suppose that
S
i
n
=
S
i
n
+
1
= · · · =
S
i
n
+
1
−
1
⊂
S
i
n
+
1
. Set
i
1
=
k
>
1 and choose
p
1
∈
S
i
1
\
S
i
1
−
1
,
p
2
∈
S
i
2
\
S
i
2
−
1
, . . . ,
p
k
∈
S
i
k
\
S
i
k
−
1
, and
p
k
+
1
∈
S
i
k
+
1
\
S
i
k
.
Then
m
=
p
1
p
2
· · ·
p
k
∈
A
and
n
=
p
2
p
3
· · ·
p
k
+
1
∈
A
because
p
2
∈
S
i
1
=
S
k
.
Problem 1.2.15.
Let n be an integer, n
≥
2
. Show that if k
2
+
k
+
n is a prime
number for every integer k,
0
≤
k
≤
√
n
/
3
, then k
2
+
k
+
n is a prime number
for any k,
0
≤
k
≤
n
−
2
.
(28th International Mathematical Olympiad)
Solution.
It is not difficult to verify the property for
n
=
2
,
3, so we may suppose
n
≥
5. Assume the contrary. Then there is some number
√
n
/
3
<
m
≤
n
−
2
such that
m
2
+
m
+
n
is composite and
k
2
+
k
+
n
is prime for
k
<
m
. Note
that
(
−
k
−
1
)
2
+
(
−
k
−
1
)
+
n
=
k
2
+
k
+
n
. Therefore
k
2
+
k
+
n
is prime
for
−
m
≤
k
<
m
. Let
m
2
+
m
+
n
=
ab
be a nontrivial decomposition such
that 1
<
a
≤
b
. Since
n
<
3
m
2
,
ab
=
m
2
+
m
+
n
<
4
m
2
+
m
< (
2
m
+
1
)
2
.
Therefore
a
<
2
m
+
1 and
−
m
≤
m
−
a
<
m
. Therefore
(
m
−
a
)
2
+
(
m
−
a
)
+
n
is a prime number. However,
(
m
−
a
)
2
+
(
m
−
a
)
+
n
=
m
2
+
m
+
n
+
a
(
a
−
2
m
−
1
)
=
a
(
b
+
a
−
2
m
−
1
).
It follows that
b
+
a
−
2
m
−
1
=
1 or
a
+
b
=
2
(
m
+
1
)
. By the AM–GM
inequality,
m
2
+
m
+
n
=
ab
≤
(
a
+
b
)
2
4
=
(
m
+
1
)
2
=
m
2
+
2
m
+
1
;
hence
n
≤
m
+
1, contradicting the choice of
m
≤
n
−
2.
Remark.
The problem is related to the famous example of Euler of a polynomial
generator of primes:
x
2
+
x
+
41 produces primes for 0
≤
x
≤
39. The problem
shows that it suffices to check the primality only for the first four values of
x
.
Problem 1.2.16.
A sequence q
1
,
q
2
, . . .
of primes satisfies the following condi-
tion: for n
≥
3
, q
n
is the greatest prime divisor of q
n
−
1
+
q
n
−
2
+
2000
. Prove that
the sequence is bounded.
(2000 Polish Mathematical Olympiad)
Solution.
Let
b
n
=
max
{
q
n
,
q
n
+
1
}
for
n
≥
1. We first prove that
b
n
+
1
≤
b
n
+
2002
for all such
n
. Certainly
q
n
+
1
≤
b
n
, so it suffices to show that
q
n
+
2
≤
b
n
+
2002.
If either
q
n
or
q
n
+
1
equals 2, then we have
q
n
+
2
≤
q
n
+
q
n
+
1
+
2000
=
b
n
+
2002.
Do'stlaringiz bilan baham: |
