Number Theory: Structures, Examples, and Problems

Part I, Section 5.3).
5.4
Inclusion–Exclusion
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 chang-
ing 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)
First solution.
It is possible. We begin by proving the following lemma:
Lemma.
Given a set S of positive integers, there is a subset T
⊆
S such that
every element of S divides an odd number of elements in T .
Proof.
We prove the claim by induction on
|
S
|
, the number of elements in
S
. If
|
S
| =
1 then let
T
=
S
.
If
|
S
|
>
1, then let
a
be the smallest element of
S
. Consider the set
S
=
S
\{
a
}
,
the set of the largest
|
S
| −
1 elements in
S
. By induction there is a subset
T
⊆
S
such that every element in
S
divides an odd number of elements in
T
.
If
a
also divides an odd number of elements in
T
, then the set
T
=
T
suffices.
Otherwise, consider the set
T
=
T
∪ {
a
}
. Thus
a
divides an odd number of

---