|
I Fundamentals, 1. Divisibility
prime, so
(
a
−
4
)(
a
−
2
)
a
divides
n
. It follows that
(
a
−
4
)(
a
−
2
)
a
≤
(
a
+
2
)
2
, so
a
3
−
6
a
2
+
8
a
≤
a
2
+
4
a
+
4. Then
a
3
−
7
a
2
+
4
a
−
4
≤
0 or
a
2
(
a
−
7
)
+
4
(
a
−
1
)
≤
0.
This is false, because
a
≥
7; hence
a
=
1
,
3, or 5.
If
a
=
1, then 1
2
≤
n
≤
3
2
, so
n
∈ {
1
,
2
, . . . ,
8
}
.
If
a
=
3, then 3
2
≤
n
≤
5
2
and 1
·
3
|
n
, so
n
∈ {
9
,
12
,
15
,
18
,
21
,
24
}
.
If
a
=
5, then 5
2
≤
n
≤
7
2
and 1
·
3
·
5
|
n
, so
n
∈ {
30
,
45
}
. Therefore
n
∈ {
1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
,
9
,
12
,
15
,
18
,
21
,
24
,
30
,
45
}
.
Problem 1.1.5.
Find the elements of the set
S
=
x
∈
Z
x
3
−
3
x
+
2
2
x
+
1
∈
Z
.
Solution.
Since
x
3
−
3
x
+
2
2
x
+
1
∈
Z
, then
8
x
3
−
24
x
+
16
2
x
+
1
=
4
x
2
−
2
x
−
11
+
27
2
x
+
1
∈
Z
.
It follows that 2
x
+
1 divides 27, so
2
x
+
1
∈ {±
1
,
±
3
,
±
9
,
±
27
}
and
x
∈ {−
14
,
−
5
,
−
2
,
−
1
,
0
,
1
,
4
,
13
}
,
since 2
x
+
1 is odd,
x
3
−
3
x
+
2
2
x
+
1
∈
Z
⇔
8
x
3
−
24
x
+
16
2
x
+
1
∈
Z
, so all these are solutions.
Problem 1.1.6.
Find all positive integers n for which the number obtained by
erasing the last digit is a divisor of n.
Solution.
Let
b
be the last digit of the number
n
and let
a
be the number obtained
from
n
by erasing the last digit
b
. Then
n
=
10
a
+
b
. Since
a
is a divisor of
n
,
we infer that
a
divides
b
. Any number
n
that ends in 0 is therefore a solution. If
b
=
0, then
a
is a digit and
n
is one of the numbers 11, 12,
. . .
, 19, 22, 24, 26,
28, 33, 36, 39, 44, 48, 55, 66, 77, 88, 99.
Problem 1.1.7.
Find the greatest positive integer x such that
23
6
+
x
divides
2000
!
.
Solution.
The number 23 is prime and divides every 23rd number. In all, there
are
2000
23
=
86 numbers from 1 to 2000 that are divisible by 23. Among those
86 numbers, three of them, namely 23
2
, 2
·
23
2
, and 3
·
23
2
, are divisible by 23
2
.
Hence 23
89
|
2000
!
and
x
=
89
−
6
=
83.
Problem 1.1.8.
Find all positive integers a
,
b
,
c such that
ab
+
bc
+
ac
>
abc
.
Solution.
Assume that
a
≤
b
≤
c
. If
a
≥
3 then
ab
+
bc
+
ac
≤
3
bc
≤
abc
, a
contradiction. Since
a
is an integer, all that is left is that
a
=
2 or
a
=
1.
If
a
=
2, then the inequality becomes 2
b
+
2
c
+
bc
>
2
bc
; hence
1
c
+
1
b
>
1
2
.
1.1. Divisibility
7
If
b
≥
5, then
c
≥
5 and
1
2
<
1
b
+
1
c
<
1
5
+
1
5
=
2
5
,
which is false.
Therefore
b
<
5, that is,
b
=
4,
b
=
3, or
b
=
2.
The case
b
=
4 gives
c
<
4, which is not possible, since
b
≤
c
.
If
b
=
3, then we get
c
<
6, whence
c
∈ {
3
,
4
,
5
}
. In this case we find the
triples
(
2
,
3
,
3
)
,
(
2
,
3
,
4
)
,
(
2
,
3
,
5
)
.
If
b
=
2, then we find the solutions
(
2
,
2
,
c
)
, where
c
is any positive integer.
If
a
=
1, then the solutions are
(
1
,
b
,
c
)
, where
b
and
c
are any positive
integers.
In conclusion, the solutions are given by the triples
(
2
,
3
,
3
)
,
(
2
,
3
,
4
)
,
(
2
,
3
,
5
)
,
(
2
,
2
,
c
)
,
(
1
,
b
,
c
)
, where
b
,
c
are arbitrary positive integers. Because of symmetry
we have also to consider all permutations.
Problem 1.1.9.
Let n be a positive integer. Show that any number greater than
n
4
/
16
can be written in at most one way as the product of two of its divisors
having difference not exceeding n.
(1998 St. Petersburg City Mathematical Olympiad)
First Solution.
Suppose, on the contrary, that there exist
a
>
c
≥
d
>
b
with
a
−
b
≤
n
and
ab
=
cd
>
n
4
/
16. Put
p
=
a
+
b
,
q
=
a
−
b
,
r
=
c
+
d
,
s
=
c
−
d
.
Now
p
2
−
q
2
=
4
ab
=
4
cd
=
r
2
−
s
2
>
n
4
/
4
.
Thus
p
2
−
r
2
=
q
2
−
s
2
≤
q
2
≤
n
2
. But
r
2
>
n
4
/
4 (so
r
>
n
2
/
2) and
p
>
r
, so
p
2
−
r
2
> (
n
2
/
2
+
1
)
2
−
(
n
2
/
2
)
2
≥
n
2
+
1
,
a contradiction.
Second solution.
Suppose
a
<
c
≤
d
<
b
with
ab
=
cd
=
N
and
b
−
a
≤
n
.
Note that
(
a
+
b
)
2
−
n
2
≤
(
a
+
b
)
2
−
(
b
−
a
)
2
=
4
ab
=
4
cd
=
(
c
+
d
)
2
−
(
d
−
c
)
2
≤
(
c
+
d
)
2
,
so that
(
a
+
b
)
2
−
(
c
+
d
)
2
≤
n
2
. But since
a
+
b
>
c
+
d
(since the function
f
:
x
→
x
+
N
/
x
decreases for
N
<
√
x
, which means that
f
(
a
) >
f
(
c
)
), we
obtain
n
2
≥
(
c
+
d
+
1
)
2
−
(
c
+
d
)
2
=
2
c
+
2
d
+
1
.
Finally, the arithmetic–geometric means (AM–GM) inequality (see the glossary)
gives
N
=
cd
≤
c
+
d
2
2
≤
(
n
2
−
1
)
2
16
<
n
4
16
,
proving the claim.
8
I Fundamentals, 1. Divisibility
Additional Problems
Problem 1.1.10.
Show that for any natural number
n
≥
2, one can find three
distinct natural numbers
a
,
b
,
c
between
n
2
and
(
n
+
1
)
2
such that
a
2
+
b
2
is
divisible by
c
.
(1998 St. Petersburg City Mathematical Olympiad)
Problem 1.1.11.
Find all odd integers
n
greater than 1 such that for any relatively
prime divisors
a
and
b
of
n
, the number
a
+
b
−
1 is also a divisor of
n
.
(2001 Russian Mathematical Olympiad)
Problem 1.1.12.
Find all positive integers
n
such that 3
n
−
1
+
5
n
−
1
divides 3
n
+
5
n
.
(1996 St. Petersburg City Mathematical Olympiad)
Problem 1.1.13.
Find all positive integers
n
such that the set
{
n
,
n
+
1
,
n
+
2
,
n
+
3
,
n
+
4
,
n
+
5
}
can be split into two disjoint subsets such that the products of elements in these
subsets are the same.
(12th International Mathematical Olympiad)
Problem 1.1.14.
The positive integers
d
1
,
d
2
, . . . ,
d
n
are distinct divisors of 1995.
Prove that there exist
d
i
and
d
j
among them such that the numerator of the reduced
fraction
d
i
/
d
j
is at least
n
.
(1995 Israeli Mathematical Olympiad)
Problem 1.1.15.
Determine all pairs
(
a
,
b
)
of positive integers such that
ab
2
+
b
+
7 divides
a
2
b
+
a
+
b
.
(39th International Mathematical Olympiad)
Problem 1.1.16.
Find all integers
a
,
b
,
c
with 1
<
a
<
b
<
c
such that
(
a
−
1
)(
b
−
1
)(
c
−
1
)
is a divisor of
abc
−
1.
(33rd International Mathematical Olympiad)
Problem 1.1.17.
Find all pairs of positive integers
(
x
,
y
)
for which
x
2
+
y
2
x
−
y
is an integer that divides 1995.
(1995 Bulgarian Mathematical Olympiad)
Do'stlaringiz bilan baham: |
