|
9.3. Sequences of Integers
349
Then for
m
<
3
t
, observe that
r
m
=
r
m
+
3
t
=
r
m
+
2
·
3
t
and
s
m
=
s
m
+
3
t
=
s
m
+
2
·
3
t
,
so that
x
m
−
x
m
−
1
=
x
3
t
+
m
−
x
3
t
+
m
−
1
=
x
2
·
3
t
+
m
−
x
2
·
3
t
+
m
−
1
.
Setting
m
=
1
,
2
, . . . ,
k
<
3
t
and adding the resulting equations, we have
x
k
=
x
3
t
+
k
−
x
3
t
x
k
=
x
2
·
3
t
+
k
−
x
2
·
3
t
.
Now setting
n
=
3
t
in the recursion and using (ii) from the induction hypoth-
esis, we have
x
3
t
=
3
t
, and
{
x
3
t
, . . . ,
x
2
·
3
t
−
2
} =
3
t
+
3
2
, . . . ,
3
t
+
1
−
1
2
,
x
2
·
3
t
−
1
=
3
t
+
1
2
.
Then setting
n
=
2
·
3
t
in the recursion, we have
x
2
·
3
t
= −
3
t
, giving
{
x
2
·
3
t
, . . . ,
x
3
t
+
1
−
2
} =
−
3
t
+
1
−
3
2
, . . . ,
3
t
+
1
2
x
2
·
3
t
+
1
−
1
= −
3
t
+
1
−
1
2
.
Combining this with (i) and (ii) from the induction hypothesis proves the
claims for
t
+
1. This completes the proof.
Second solution.
For
n
i
∈ {−
1
,
0
,
1
}
, let the number
[
n
m
n
m
−
1
· · ·
n
0
]
in base 3 equals
"
m
i
=
0
n
i
·
3
i
. It is simple to prove by induction on
k
that the
base-3 numbers with at most
k
digits equal
−
3
k
−
1
2
,
−
3
k
−
3
2
, . . . ,
3
k
−
1
2
,
which implies that every integer has a unique representation in base 3.
Now we prove by induction on
n
that if
n
=
a
m
a
m
−
1
· · ·
a
0
in base 3, then
x
n
= [
b
m
b
m
−
1
. . .
b
0
]
in base 3, where
b
i
= −
1 if
a
i
=
2 and
b
i
=
a
i
for all
other cases.
350
II Solutions, 9. Some Special Problems in Number Theory
For the base case,
x
0
=
0
= [
0
]
. Now assume that the claim is true for
n
−
1.
If
n
=
a
m
a
m
−
1
· · ·
a
r
+
1
1 00
. . .
0
r
, then
x
n
=
x
n
−
1
+
3
r
+
1
−
1
2
= [
b
m
b
m
−
1
. . .
b
i
0
−
1
−
1
· · · −
1
r
] + [
11
. . .
1
r
+
1
]
= [
b
m
b
m
−
1
. . .
b
i
1 00
. . .
0
r
]
.
If instead
n
=
a
m
a
m
−
1
· · ·
a
i
2 00
. . .
0
r
, then
x
n
=
x
n
−
1
+
A
−
3
r
+
1
+
1
2
B
= [
b
m
b
m
−
1
. . .
b
i
1
−
1
−
1
· · · −
1
r
] + [−
1 11
. . .
1
r
+
1
]
= [
b
m
b
m
−
1
. . .
b
i
−
1 00
. . .
0
r
]
.
In either case, the claim is true for
n
, completing the induction.
To finish the proof, note that every integer appears exactly once in base 3.
Thus each integer appears exactly once in
{
x
n
}
n
≥
0
, as desired.
Problem 9.3.33.
Suppose that a
1
,
a
2
, . . .
is a sequence of natural numbers such
that for all natural numbers m and n,
gcd
(
a
m
,
a
n
)
=
a
gcd
(
m
,
n
)
. Prove that there
exists a sequence b
1
,
b
2
, . . .
of natural numbers such that a
n
=
d
|
n
b
d
for all
integers n
≥
1
.
(2001 Iranian Mathematical Olympiad)
First solution.
For each
n
, let rad
(
n
)
denote the largest square-free divisor of
n
(i.e., the product of all distinct prime factors of
n
). We let
b
n
equal to the ratio of
the following two numbers:
•
E
n
, the product of all
a
n
/
d
such that
d
is square-free, divides
n
, and has an
even number of prime factors.
•
O
n
, the product of all
a
n
/
d
such that
d
is square-free, divides
n
, and has an
odd number of prime factors.
Lemma 1.
d
|
a
n
b
d
=
a
n
.
9.3. Sequences of Integers
351
Proof.
Fix
n
, and observe that
d
|
n
b
n
equals
d
|
n
E
d
d
|
n
O
d
=
d
|
n
a
μ(
d
)
n
/
d
,
(
∗
)
where
μ
is the M¨obius function.
In the numerator of
(
∗
)
, each
E
d
is the product of
a
m
such that
m
|
d
. Also,
d
|
n
, implying that the numerator is the product of various
a
m
such that
m
|
n
.
For fixed
m
that divides
n
, how many times does
a
m
appears in the numerator
d
|
n
E
d
of
(
∗
)
?
If
a
m
appears in
E
d
and
d
|
n
, then let
t
=
d
/
m
. By the definition of
E
d
,
we know that (i)
t
is square-free and (ii)
t
has an even number of prime factors.
Because
d
|
n
and
t
=
d
/
m
, we further know that (iii)
t
divides
n
/
m
.
Conversely, suppose that
t
is any positive integer satisfying (i), (ii), and (iii),
and write
d
=
tm
. By (iii),
d
is a divisor of
n
. Also,
t
is square-free by (i), is a
divisor of
d
, and has an even number of prime factors by (ii). Thus,
a
m
appears in
E
d
.
Suppose that
n
/
m
has
l
distinct prime factors. Then it has
l
0
+
l
2
+ · · ·
factors
t
satisfying (i), (ii), and (iii), implying that
a
m
appears in the numerator of
(
∗
)
exactly
l
0
+
l
2
+ · · ·
times. Similarly,
a
m
appears in the denominator of
(
∗
)
exactly
l
1
+
l
3
+ · · ·
times. If
m
<
n
, then
l
≥
1, and these expressions are equal, so that the
a
m
’s
in the numerator and denominator of
(
∗
)
cancel each other out. If
m
=
n
, then
l
=
0, so that
a
n
appears in the numerator once and in the denominator zero times.
Therefore,
d
|
n
b
d
=
d
|
n
E
d
d
|
n
O
d
=
a
n
,
as desired.
Lemma 2.
For any integer
α
that divides some term in a
1
,
a
2
, . . .
, there exists an
integer d such that
α
|
a
n
⇔
d
|
n
.
Proof.
Of all the integers
n
such that
α
|
a
n
, let
d
be the smallest.
If
α
|
a
n
, then
α
|
gcd
(
a
d
,
a
n
)
=
a
gcd
(
d
,
n
)
. By the minimality of
d
, gcd
(
d
,
n
)
≥
d
. But gcd
(
d
,
n
)
|
n
as well, implying gcd
(
d
,
n
)
=
d
. Hence,
d
|
n
.
If
d
|
n
, then gcd
(
a
d
,
a
n
)
=
a
gcd
(
d
,
n
)
=
a
d
. Thus,
a
d
|
a
n
. Because
α
|
a
d
, it
follows that
α
|
a
n
as well.
352
Do'stlaringiz bilan baham: |
