|
5.4. Inclusion–Exclusion
101
Proof.
Let
A
=
n
4
i
=
1
S
i
and
B
=
n
3
i
=
1
S
i
.
It is clear that
A
∪
B
=
S
and
A
∩
B
= ∅
. Hence
|
S
| = |
A
| + |
B
|
and the
conclusion follows from Theorem 5.4.1.
Example.
How many positive integers not exceeding
120
are not divisible by
2
,
3
, and
5
?
Solution.
Consider the sets
S
1
= {
2
m
|
1
≤
m
≤
60
}
,
S
2
= {
3
n
|
1
≤
n
≤
40
}
,
S
3
= {
5
p
|
1
≤
p
≤
24
}
.
We have
S
1
∩
S
2
= {
6
q
|
1
≤
q
≤
20
}
,
S
1
∩
S
3
= {
10
r
|
1
≤
r
≤
12
}
,
S
2
∩
S
3
= {
15
s
|
1
≤
s
≤
8
}
,
and
S
1
∩
S
2
∩
S
3
= {
30
u
|
1
≤
u
≤
4
}
.
Applying the formula in Theorem 5.3.2, we get
|
S
1
∩
S
2
∩
S
3
| =
120
−
(
|
S
1
| + |
S
2
| + |
S
3
|
)
+ |
S
1
∩
S
2
| + |
S
1
∩
S
3
|
+ |
S
2
∩
S
3
| − |
S
1
∩
S
2
∩
S
3
|
=
120
−
(
60
+
40
+
24
)
+
20
+
12
+
8
−
4
=
32
.
Problem 5.4.1.
Let S
= {
1
,
2
,
3
, . . . ,
280
}
. Find the smallest integer n such that
each n-element subset of S contains five numbers that are pairwise relatively
prime.
(32nd International Mathematical Olympiad)
Solution.
The solution is given in two steps.
First step. Consider the sets
M
2
= {
2
,
4
,
6
, . . . ,
280
}
,
M
3
= {
3
,
6
,
9
, . . . ,
279
}
,
M
5
= {
5
,
10
,
15
, . . . ,
280
}
,
M
7
= {
7
,
14
, . . . ,
280
}
,
and let
M
=
M
2
∪
M
3
∪
M
5
∪
M
7
. The following cardinalities are obvious:
|
M
2
| =
140
,
|
M
3
| =
93
,
|
M
5
| =
56
,
and
|
M
7
| =
40
.
102
I Fundamentals, 5. Basic Principles in Number Theory
It is easy to prove that
|
M
2
∩
M
3
| =
#
280
6
$
=
46
,
|
M
2
∩
M
5
| =
#
280
10
$
=
28
,
|
M
2
∩
M
7
| =
#
280
14
$
=
20
,
|
M
3
∩
M
5
| =
#
280
15
$
=
18
,
|
M
3
∩
M
7
| =
#
280
21
$
=
13
,
|
M
5
∩
M
7
| =
#
280
35
$
=
8
,
|
M
2
∩
M
3
∩
M
5
| =
#
280
30
$
=
9
,
|
M
2
∩
M
3
∩
M
7
| =
#
280
42
$
=
6
,
|
M
2
∩
M
5
∩
M
7
| =
#
280
70
$
=
4
,
|
M
4
∩
M
5
∩
M
7
| =
#
28
105
$
=
2
,
and
|
M
2
∩
M
3
∩
M
5
∩
M
7
| =
#
280
210
$
=
1
.
By the principle of inclusion–exclusion, we obtain
|
M
| = |
M
2
∪
M
3
∪
M
5
∪
M
7
|
=
140
+
93
+
56
+
40
−
(
46
+
28
+
20
+
18
+
13
+
8
)
+
(
9
+
6
+
4
+
2
)
−
1
=
216
.
By the pigeonhole principle, any five-element subset of
M
contains at least
two elements from the same subset
M
i
,
i
∈ {
2
,
3
,
5
,
7
}
. These elements are not
relatively prime numbers. Thus, we have proved that
n
>
216.
Second step. We will prove that
n
=
217.
The set
S
\
M
contains 280
−
216
=
64 elements. It contains prime numbers
and composite numbers. Taking into account that
√
280
=
16, we see that any
composite numbers in
S
\
M
have one prime factor at most 16. Thus they are
precisely
C
= {
11
2
;
11
·
13
;
11
·
17
;
11
·
19
;
11
·
23
;
13
2
;
13
·
17
;
13
·
19
}
.
Observe that
|
C
| =
8. The set
S
\
M
contains the number 1, 8 composite
numbers, and 55 prime numbers. Also, taking into account the prime numbers 2,
3, 5, 7, we infer that the set
S
contains 59 prime numbers in all.
Let
p
1
=
2,
p
2
=
3,
p
3
=
5
, . . . ,
p
59
be all these prime numbers and let
P
= {
1
,
p
2
,
p
2
, . . . ,
p
59
}
. Thus,
|
P
| =
60.
Let
T
be a subset containing 217 elements of
S
. If
|
T
∩
P
| ≥
5, it follows that
T
contains 5 elements that are relatively prime numbers. So, suppose
|
T
∩
P
| ≤
4.
In this case,
|
T
∩
(
S
\
P
)
| ≥
217
−
4
=
213. Since
S
contains 220 composite
numbers, it follows that at most 7 composite numbers are not in
T
.
5.4. Inclusion–Exclusion
103
Consider the following five-element subsets of
S
\
P
:
A
1
= {
2
2
;
3
2
;
5
2
;
7
2
;
13
2
}
,
A
2
= {
2
·
23
;
3
·
19
;
5
·
17
;
7
·
13
;
11
·
11
}
,
A
3
= {
2
·
29
;
3
·
23
;
5
·
19
;
7
·
17
;
11
·
13
}
,
A
4
= {
2
·
31
;
3
·
29
;
5
·
23
;
7
·
19
;
11
·
17
}
,
A
5
= {
2
·
37
;
3
·
31
;
5
·
29
;
7
·
23
;
11
·
19
}
,
A
6
= {
2
·
41
;
3
·
37
;
5
·
31
;
7
·
29
;
11
·
23
}
,
A
7
= {
2
·
43
;
3
·
41
;
5
·
37
;
7
·
23
;
13
·
17
}
,
A
8
= {
2
·
47
;
3
·
43
;
5
·
41
;
7
·
37
;
13
·
19
}
.
By the pigeonhole principle, there exists a set
A
i
, 1
≤
i
≤
8, such that
A
i
⊂
T
; if not, the set
S
\
T
would contain eight composite numbers. Each
A
i
contains
five relatively prime numbers and we are done.
Additional Problems
Problem 5.4.2.
The numbers from 1 to 1
,
000
,
000 can be colored black or white.
A permissible move consists in selecting a number from 1 to 1
,
000
,
000 and
changing the color of that number and each number not relatively prime to it.
Initially all of the numbers are black. Is it possible to make a sequence of moves
after which all of the numbers are colored white?
(1999 Russian Mathematical Olympiad)
6
Arithmetic Functions
6.1
Multiplicative Functions
Arithmetic functions are defined on the positive integers and are complex val-
ued. The arithmetic function
f
=
0 is called
multiplicative
if for every pair of
relatively prime positive integers
m
and
n
,
f
(
mn
)
=
f
(
m
)
f
(
n
).
An arithmetic function
f
=
0 is called
completely multiplicative
if the relation
above holds for all positive integers
m
and
n
.
Remarks.
(1) If
f
:
Z
∗
+
→
C
is multiplicative, then
f
(
1
)
=
1. Indeed, if
a
is
a positive integer for which
f
(
a
)
=
0, then
f
(
a
)
=
f
(
a
·
1
)
=
f
(
a
)
f
(
1
)
and
dividing by
f
(
a
)
yields
f
(
1
)
=
1.
(2) If
f
is multiplicative and
n
=
p
α
1
1
· · ·
p
α
k
k
is the prime factorization of the
positive integer
n
, then
f
(
n
)
=
f
(
p
α
1
1
)
· · ·
f
(
p
α
k
k
)
; that is, in order to compute
f
(
n
)
it suffices to compute
f
(
p
α
i
i
)
,
i
=
1
, . . . ,
k
.
(3) If
f
is completely multiplicative and
n
=
p
α
1
1
· · ·
p
α
k
k
is the prime factor-
ization of
n
, then
f
(
n
)
=
f
(
p
1
)
α
1
· · ·
f
(
p
k
)
α
k
; that is, in order to compute
f
(
n
)
it suffices to compute
f
(
p
i
)
,
i
=
1
, . . . ,
k
.
An important arithmetic function is the
M¨obius
1
function
defined by
μ(
n
)
=
⎧
⎨
⎩
1
if
n
=
1
,
0
if
p
2
|
n
for some prime
p
,
(
−
1
)
k
if
n
=
p
1
· · ·
p
k
,
where
p
1
, . . . ,
p
k
are distinct primes.
For example,
μ(
2
)
= −
1,
μ(
6
)
=
1,
μ(
12
)
=
μ(
2
2
·
3
)
=
0.
1
August Ferdinand M¨obius (1790–1868), German mathematician best known for his work in topol-
ogy, especially for his conception of the M¨obius strip, a two-dimensional surface with only one side.
© Birkhäuser Boston, a part of Springer Science + Business Media, LLC 2009
105
T. Andreescu and D. Andrica,
Number Theory
,
DOI: 10.1007/
_6,
b11856
106
Do'stlaringiz bilan baham: |
