|
I Fundamentals, 9. Some Special Problems in Number Theory
Additional Problems
Problem 9.2.9.
Prove that if
n
is an even perfect number, then 8
n
+
1 is a perfect
square.
Problem 9.2.10.
Show that if
k
is an odd positive integer, then 2
k
−
1
M
k
can be
written as the sum of the cubes of the first 2
k
−
1
2
odd positive integers. In particular,
any perfect number has this property.
9.3
Sequences of Integers
9.3.1
Fibonacci and Lucas Sequences
Leonardo Fibonacci
3
introduced in 1228 the sequence
F
1
=
F
2
=
1 and
F
n
+
1
=
F
n
+
F
n
−
1
,
n
≥
2. It is not difficult to prove by induction that the closed form for
F
n
is given by Binet’s formula
F
n
=
1
√
5
1
+
√
5
2
n
−
1
−
√
5
2
n
(
1
)
for all
n
≥
1. As a consequence of the recursive definition or of formula above,
it is a convention to define
F
0
=
0. Identities for Fibonacci numbers are usually
proved either by induction or from Binet’s formula. It is also an useful matrix
form for the Fibonacci numbers
1 1
1 0
n
=
F
n
+
1
F
n
F
n
F
n
−
1
,
n
≥
1
(
2
)
that easily follows by induction.
In what follows we give some arithmetical properties of the Fibonacci num-
bers.
(1) If
m
|
n
, then
F
m
|
F
n
. If
n
≥
5 and
F
n
is a prime, then so is
n
.
(2) For any
m
,
n
≥
0, gcd
(
F
m
,
F
n
)
=
F
gcd
(
m
,
n
)
.
(3) If gcd
(
m
,
n
)
=
1, then
F
m
F
n
|
F
mn
.
In order to prove (1) suppose that
n
=
mk
for some integer
k
>
1 and denote
α
=
1
+
√
5
2
,
β
=
1
−
√
5
2
. Using (1), we have
F
n
F
m
=
α
n
−
β
n
α
m
−
β
m
=
(α
m
)
k
−
(β
m
)
k
α
m
−
β
m
=
α
m
(
k
−
1
)
+
α
m
(
k
−
2
)
β
m
+ · · · +
β
m
(
k
−
1
)
.
3
Leonardo Pisano Fibonacci (1170–1250) was among the first to introduce the Hindu-Arabic num-
ber system into Europe. His book on how to do arithmetic in the decimal system, called
Liber abbaci
(meaning
Book of the Abacus
or
Book of Calculating
), completed in 1202, persuaded many European
mathematicians of his day to use this “new” system.
9.3. Sequences of Integers
181
Because
α
+
β
=
1 and
αβ
= −
1 it follows by induction that
α
i
+
β
i
is an
integer for all integers
i
≥
1 and the conclusion follows.
It is now clear that if
n
=
kh
,
k
≥
3, then
F
k
divides
F
n
hence
F
n
is not a
prime.
For (2) let
d
=
gcd
(
m
,
n
)
and suppose that
n
>
m
. Applying Euclid’s Algo-
rithm, we get
n
=
mq
1
+
r
1
m
=
r
1
q
2
+
r
2
r
1
=
r
2
q
3
+
r
3
. . .
r
i
−
1
=
r
i
q
i
+
1
and so
d
=
r
i
. It is not difficult to check that for any positive integers
m
,
n
,
F
m
+
n
=
F
m
−
1
F
n
+
F
m
F
n
+
1
.
(
3
)
The standard proof of (3) is by induction on
n
after fixing
m
. Another argu-
ment follows from the matrix form (2). Indeed, we have
F
m
+
n
+
1
F
m
+
n
F
m
+
n
F
m
+
n
−
1
=
1 1
1 0
m
+
n
=
1 1
1 0
n
1 1
1 0
m
=
F
n
+
1
F
n
F
n
F
n
−
1
F
m
+
1
F
m
F
m
F
m
−
1
=
F
n
+
1
F
m
+
1
+
F
n
F
m
F
n
+
1
F
m
+
F
n
F
m
−
1
F
n
F
m
+
1
+
F
n
−
1
F
m
F
n
F
m
+
F
n
−
1
F
m
−
1
.
Suppose
n
>
m
≥
1. From the identity
F
n
=
F
m
−
1
F
n
−
m
+
F
m
F
n
−
m
+
1
we
have
gcd
(
F
m
,
F
n
)
=
gcd
(
F
m
,
F
m
−
1
F
n
−
m
+
F
m
F
n
−
m
+
1
)
=
gcd
(
F
m
,
F
m
−
1
F
n
−
m
).
By the inductive hypothesis,
gcd
(
F
m
,
F
m
−
1
)
=
F
1
=
1
and
gcd
(
F
m
,
F
n
−
m
)
=
F
gcd
(
m
,
n
−
m
)
=
F
gcd
(
m
,
n
)
.
Therefore gcd
(
F
m
,
F
n
)
=
F
gcd
(
m
,
n
)
.
Property (3) follows from (2) by observing that
gcd
(
F
m
,
F
n
)
=
F
gcd
(
m
,
n
)
=
F
1
=
1
and then using (1).
182
I Fundamentals, 9. Some Special Problems in Number Theory
Lucas’s sequence is defined by
L
0
=
2,
L
1
=
1, and
L
n
+
1
=
L
n
+
L
n
−
1
,
n
≥
1. The Lucas numbers are the companions to the Fibonacci numbers because
they satisfy the same recursion.
The analogue of Binet’s Fibonacci number formula for Lucas numbers is
L
n
=
1
+
√
5
2
n
+
1
−
√
5
2
n
,
n
≥
0
,
(
4
)
and they are connected with Fibonacci numbers by
L
n
=
F
2
n
/
F
n
,
L
n
=
2
F
n
+
1
−
F
n
,
n
≥
0.
Problem 9.3.1.
Show that there is a positive number in the Fibonacci sequence
that is divisible by
1000
.
(1999 Irish Mathematical Olympiad)
Solution.
In fact, for any natural number
n
, there exist infinitely many positive
Fibonacci numbers divisible by
n
.
Consider ordered pairs of consecutive Fibonacci numbers
(
F
0
,
F
1
)
,
(
F
1
,
F
2
),
. . .
taken modulo
n
. Because the Fibonacci sequence is infinite and there are only
n
2
possible ordered pairs of integers modulo
n
, two such pairs
(
F
j
,
F
j
+
1
)
must
be congruent:
F
i
≡
F
i
+
m
and
F
i
+
1
≡
F
i
+
m
+
1
(
mod
n
)
for some
i
and
m
.
If
i
≥
1 then
F
i
−
1
≡
F
i
+
1
−
F
i
≡
F
i
+
m
+
1
−
F
i
+
m
≡
F
i
+
m
−
1
(
mod
n
)
.
Likewise,
F
i
+
2
≡
F
i
+
1
+
F
i
≡
F
i
+
m
+
1
+
F
i
+
m
≡
F
i
+
2
+
m
(
mod
n
)
. Con-
tinuing similarly, we have
F
j
≡
F
j
+
m
(
mod
n
)
for all
j
≥
0. In particular,
0
=
F
0
≡
F
m
≡
F
2
m
≡ · · ·
(
mod
n
)
, so the numbers
F
m
,
F
2
m
, . . .
are all
positive Fibonacci numbers divisible by
n
. Applying this to
n
=
1000, we are
done.
Problem 9.3.2.
Prove that
(i) The statement “F
n
+
k
−
F
n
is divisible by
10
for all positive integers n” is
true if k
=
60
and false for any positive integer k
<
60
;
(ii) The statement “F
n
+
t
−
F
n
is divisible by
100
for all positive integers n”
is true if t
=
300
and false for any positive integer t
<
300
.
(1996 Irish Mathematical Olympiad)
First solution.
A direct computation shows that the Fibonacci sequence has pe-
riod 3 modulo 2 and 20 modulo 5 (compute terms until the initial terms 0, 1 repeat,
at which time the entire sequence repeats), yielding (a). As for (b), one computes
that the period mod 4 is 6. The period mod 25 turns out to be 100, which is awfully
many terms to compute by hand, but knowing that the period must be a multiple
of 20 helps, and verifying the recursion
F
n
+
8
=
7
F
n
+
4
−
F
n
shows that the period
divides 100; finally, an explicit computation shows that the period is not 20.
Do'stlaringiz bilan baham: |
