|
1.2. Prime Numbers
225
Otherwise,
q
n
and
q
n
+
1
are both odd, so
q
n
+
q
n
+
1
+
2000 is even. In this case
q
n
+
2
=
2 divides this number; hence we have
q
n
+
2
≤
1
2
(
q
n
+
q
n
+
1
+
2000
)
=
1
2
(
q
n
+
q
n
+
1
)
+
1000
≤
b
n
+
1000
.
This proves the claim.
Choose
k
large enough that
b
1
≤
k
·
2003
! +
1. We prove by induction that
b
n
≤
k
·
2003
! +
1 for all
n
. If this statement holds for some
n
, then
b
n
+
1
≤
b
n
+
2003
≤
k
·
2003
! +
2003. However, the numbers
k
·
2003
! +
m
for 2
≤
m
≤
2003 are all composite (since
m
is a factor). Since
b
n
+
1
is prime, it follows that
b
n
+
1
≤
k
·
2003
! +
1. Thus,
q
n
≤
b
n
≤
k
·
2003
! +
1 for all
n
.
Problem 1.2.17.
Let a
>
b
>
c
>
d be positive integers and suppose
ac
+
bd
=
(
b
+
d
+
a
−
c
)(
b
+
d
−
a
+
c
).
Prove that ab
+
cd is not prime.
(42nd International Mathematical Olympiad)
Solution.
The given equality is equivalent to
a
2
−
ac
+
c
2
=
b
2
+
bd
+
d
2
. Hence
(
ab
+
cd
)(
ad
+
bc
)
=
ac
(
b
2
+
bd
+
d
2
)
+
bd
(
a
2
−
ac
+
c
2
),
that is,
(
ab
+
cd
)(
ad
+
bc
)
=
(
ac
+
bd
)(
a
2
−
ac
+
c
2
).
(
1
)
Now suppose that
ab
+
cd
is prime. It follows from
a
>
b
>
c
>
d
that
ab
+
cd
>
ac
+
bd
>
ad
+
bc
;
(
2
)
hence
ac
+
bd
is relatively prime to
ab
+
cd
. But then (1) implies that
ac
+
bd
divides
ad
+
bc
, which is impossible by (2).
Problem 1.2.18.
Find the least odd positive integer
n
such that for each prime
p
,
n
2
−
1
4
+
np
4
+
p
8
is divisible by at least four primes.
(Mathematical Reflections)
First solution.
Let
n
=
2
k
+
1 with
k
a nonnegative integer. For
k
=
0
,
1
,
2
,
3 it
is easy to see that when
p
=
2 there are fewer than four prime divisors:
M
=
p
8
+
np
4
+
n
2
−
1
4
=
p
4
+
n
2
2
−
1
4
=
p
4
+
n
−
1
2
p
4
+
n
+
1
2
=
(
p
4
+
k
)(
p
4
+
k
+
1
).
226
II Solutions, 1. Divisibility
Let
k
=
4. Then
M
=
(
p
4
+
4
)(
p
4
+
5
)
=
(
p
2
+
2
p
+
2
)(
p
2
−
2
p
+
2
)(
p
4
+
5
).
If
p
=
2, then
m
is divisible by 2, 3, 5, 7. If
p
is odd we have
gcd
(
p
2
+
2
p
+
2
,
p
2
−
2
p
+
2
)
=
gcd
(
p
2
+
2
p
+
2
,
4
p
)
=
1
,
gcd
(
p
2
+
2
p
+
2
,
p
4
+
5
)
=
gcd
(
p
2
+
2
p
+
2
,
p
4
+
5
−
p
4
−
4
−
4
p
3
−
4
p
)
=
gcd
(
p
2
+
2
p
+
2
,
4
p
3
+
8
p
2
+
4
p
+
1
)
=
gcd
(
p
2
+
2
p
+
2
,
4
p
3
+
8
p
2
+
4
p
+
1
−
4
p
3
−
8
p
2
−
4
p
)
=
gcd
(
p
2
+
2
p
+
2
,
1
)
=
1
,
and
gcd
(
p
2
−
2
p
+
2
,
p
4
+
5
)
=
gcd
(
p
2
−
2
p
+
2
,
4
p
3
−
8
p
2
+
4
p
+
1
)
=
gcd
(
p
2
−
2
p
+
2
,
1
)
=
1
.
Thus
p
2
+
2
p
+
2,
p
2
−
2
p
+
2, and
p
4
+
5 are pairwise coprime. Since
p
4
+
5
≡
2
(
mod 4
)
for all odd
p
, 2
1
is the greatest power of 2 dividing
p
4
+
5.
Since both
p
2
+
2
p
+
2 and
p
2
−
2
p
+
2 are odd, there is another prime different
from 2 and from the divisors of
p
2
+
2
p
+
2 and
p
2
−
2
p
+
2 that divides
p
4
+
5,
and so
n
=
9 is the least desired number.
Second solution.
Let
n
=
2
k
+
1. Then
n
2
−
1
4
+
np
4
+
p
8
=
k
(
k
+
1
)
+
(
2
k
+
1
)
p
4
+
p
8
=
(
p
4
+
k
)(
p
4
+
k
+
1
).
Note that for
k
=
0
,
1
,
2
,
3 the result does not hold for
p
=
2. We prove that
k
=
4 is the least integer that satisfies the condition. For
k
=
4 we have
(
p
4
+
4
)(
p
4
+
5
)
=
(
p
2
+
2
p
+
2
)(
p
2
−
2
p
+
2
)(
p
4
+
5
).
Since
(
p
2
+
2
p
+
2
)(
p
2
−
2
p
+
2
)
=
(
p
4
+
5
)
−
1, we have that
gcd
(
p
2
+
2
p
+
2
,
p
4
+
5
)
=
gcd
(
p
2
−
2
p
+
2
,
p
4
+
5
)
=
1
.
This implies that any prime that divides
(
p
2
+
2
p
+
2
)(
p
2
−
2
p
+
2
)
does not
divide
p
4
+
5 and vice versa. Then, it is enough to prove that two primes divide
(
p
2
+
2
p
+
2
)(
p
2
−
2
p
+
2
)
and another two divide
p
4
+
5.
1.3. The Greatest Common Divisor and Least Common Multiple
227
For
p
=
2 the result holds. Assume that
p
is an odd prime. Note that 2
|
p
4
+
5.
To prove that another prime divides
p
4
+
5 it is enough to prove that 4
p
4
+
5.
This results follows from the fact that 4
|
p
4
+
3.
In order to prove that two primes divide
(
p
2
+
2
p
+
2
)(
p
2
−
2
p
+
2
)
it is enough
to prove that
(
p
2
+
2
p
+
2
,
p
2
−
2
p
+
2
)
=
1. Let gcd
(
p
2
+
2
p
+
2
,
p
2
−
2
p
+
2
)
=
d
.
Note that
d
is odd and that
d
|
4
p
. This implies that
d
|
p
. If
d
=
p
then
p
|
p
2
+
2
p
+
2, which is a contradiction. Therefore,
d
=
1, as we wanted to
prove. This implies that
k
=
4 is the least integer value that satisfies the condition
of the problem, from which we conclude that
n
=
9 is the least odd positive
integer that satisfies the condition.
1.3
The Greatest Common Divisor and
the Least Common Multiple
Problem 1.3.9.
A sequence a
1
,
a
2
, . . .
of natural numbers satisfies
gcd
(
a
i
,
a
j
)
=
gcd
(
i
,
j
)
for all
i
=
j
.
Prove that a
i
=
i for all i .
(1995 Russian Mathematical Olympiad)
Solution.
For any integer
m
, we have gcd
(
a
m
,
a
2
m
)
=
gcd
(
2
m
,
m
)
, and so
m
|
a
m
.
This means that for any other integer
n
,
m
divides
a
n
if and only if
m
divides
gcd
(
a
m
,
a
n
)
=
gcd
(
m
,
n
)
; hence if and only if
m
|
n
. Therefore
a
n
has exactly the
same divisors as
n
and so must equal
n
for all
n
.
Problem 1.3.10.
The natural numbers a and b are such that
a
+
1
b
+
b
+
1
a
is an integer. Show that the greatest common divisor of a and b is not greater than
√
a
+
b.
(1996 Spanish Mathematical Olympiad)
Solution.
Let
d
=
gcd
(
a
,
b
)
. Adding 2, we see that
a
+
1
b
+
b
+
1
a
+
2
=
(
a
+
b
)(
a
+
b
+
1
)
ab
is an integer. Since
d
2
divides the denominator and gcd
(
d
,
a
+
b
+
1
)
=
1, we
must have
d
2
|
a
+
b
; hence
d
≤
√
a
+
b
.
228
Do'stlaringiz bilan baham: |
