Number Theory: Structures, Examples, and Problems

II Solutions, 9. Some Special Problems in Number Theory
Lemma 3.
For each positive integer n, b
n
=
E
n
/
O
n
is an integer.
Proof.
Fix
n
. Call an integer
d
a top divisor (resp. a bottom divisor) if
d
|
n
,
n
/
d
is square-free, and
n
/
d
has an even (resp. odd) number of prime factors. By
definition,
E
d
is the product of
a
d
over all top divisors
d
, and
O
d
is the product
of
a
d
over all bottom divisors
d
.
Fix any prime
p
. We show that
p
divides
E
n
at least as many times as it
divides
O
n
. To do this, it suffices to show the following for any positive integer
k
:
(1) The number of top divisors
d
with
a
d
divisible by
p
k
is greater than or
equal to the number of bottom divisors
d
with
a
d
divisible by
p
k
.
Let
k
be any positive integer. If
p
k
divides none of
a
1
,
a
2
, . . .
, then (1) holds
trivially. Otherwise, by the previous lemma, there exists an integer
d
0
such that
p
k
|
a
m
⇔
d
0
|
m
.
Hence, to show (1) it suffices to show:
(2) The number of top divisors
d
such that
d
0
|
d
, is greater than or equal to
the number of bottom divisors
d
such that
d
0
|
d
.
If
d
0
n
, then (2) holds because
d
0
does not divide
d
for any divisor
d
of
n
,
including top or bottom divisors.
Otherwise,
d
0
|
n
. For which top and bottom divisors
d
does
d
0
divide
d
?
Precisely those for which
n
/
d
divides
n
/
d
0
. If
n
/
d
0
has
l
≥
1 distinct prime
factors, then there are as many top divisors with this property as there are bottom
divisors, namely
l
0
+
l
2
+ · · · =
2
l
−
1
=
l
1
+
l
3
+ · · ·
.
If instead
d
0
=
n
and
l
=
0, then the top divisor 1 is the only value
d
with
d
|
(
n
/
d
0
)
. In either case, there are at least as many top divisors
d
with
d
|
(
n
/
d
0
)
as there are bottom divisors with the same property. Therefore, (2) holds. This
completes the proof.
Therefore,
a
n
=
d
|
n
b
d
, and
b
n
=
E
n
/
O
n
is an integer for each
n
.
Second solution.
(Gabriel Dospinescu)
Let us define
b
1
=
a
1
and
b
n
=
a
n
/
lcm
d
|
n
,
d
=
n
a
d
for
n
>
1. Of course, if
d
|
n
, then
a
d
|
a
n
and so
lcm
d
|
n
,
d
=
n
a
d
|
a
n
and
b
n
∈
Z
.
Now comes the hard part, proving that
d
|
n
b
d
=
a
n
, which is the same as
d
|
n
d
=
n
b
d
=
lcm
d
|
n
d
=
n
a
d
.
(
1
)
We will prove (1) by strong induction. For
n
=
1 it is clear.

---

9.3. Sequences of Integers
353
Now, for all
d
|
n
,
d
=
n
, by the inductive hypothesis we have
a
d
=
d
|
d
b
d
|
d
|
n
d
=
n
b
d
;
thus
d
|
n
,
d
=
n
b
d
is a multiple of lcm
d
|
n
,
d
=
n
a
d
. It remains to prove that
d
|
n
,
d
=
n
b
d
|
lcm
d
|
n
,
d
=
n
a
d
.
The essential observation is:
Lemma.
If
gcd
(
b
u
,
b
v
) >
1
, then u
|
v
or
v
|
u.
Proof.
We may assume that
u
< v
. Assume that
u
does not divide
v
. Then
b
u
=
a
u
lcm
d
|
u
d
=
u
a
d
|
a
u
a
gcd
(
u
,v)
.
Remark.
From Problem 9.3.6 (2) we have gcd
(
F
m
,
F
n
)
=
F
gcd
(
m
,
n
)
, where
F
n
is
the
n
th Fibonacci number, so this holds for
F
n
. We have
F
n
=
d
|
n
b
d
,
where
(
b
n
)
n
≥
0
is the sequence
0
,
1
,
1
,
2
,
3
,
5
,
4
,
13
,
7
,
17
,
11
,
89
,
6
,
233
,
29
,
61
,
47
,
1597
,
152
, . . . .

---

---

10
Problems Involving Binomial
Coefficients
10.1
Binomial Coefficients
Problem 10.1.7.
Show that the sequence
2002
2002
,
2003
2002
,
2004
2002
, . . . ,
considered modulo
2002
, is periodic.
(2002 Baltic Mathematical Competition)
Solution.
We will show that the sequence, taken modulo 2002, has period
m
=
2002
·
2002
!
. Indeed,
x
+
m
2002
=
(
x
+
m
)(
x
−
1
+
m
)
· · ·
(
x
−
2001
+
m
)
2002
!
=
x
(
x
−
1
)
· · ·
(
x
−
2001
)
+
km
2002
!
=
x
(
x
−
1
)
· · ·
(
x
−
2001
)
2002
!
+
2002
k
≡
x
2002
(
mod 2002
).
Problem 10.1.8.
Prove that
2
p
p
≡
2
(
mod
p
2
)
for every prime number p.
© Birkhäuser Boston, a part of Springer Science + Business Media, LLC 2009
T. Andreescu and D. Andrica, 
Number Theory
,
 
DOI: 10.1007/b11856_21, 
355

---

356
II Solutions, 10. Problems Involving Binomial Coefficients
Solution.
A short solution uses the popular Vandermonde identity
k
i
=
0
m
i
n
k
−
i
=
m
+
n
k
.
Set
m
=
n
=
k
=
p
to get
2
p
p
=
p
0
p
p
+
p
1
p
p
−
1
+ · · · +
p
p
−
1
p
1
+
p
p
p
0
.
The first and the last terms on the right-hand side equal 1. Since
p
is a prime, it
divides each binomial coefficient
p
k
for 1
≤
k
≤
p
−
1. So each of the remaining
terms is divisible by
p
2
, and hence
2
p
p
is congruent to 2 modulo
p
2
, as required.
Problem 10.1.9.
Let k
,
m
,
n be positive integers such that m
+
k
+
1
is a prime
number greater than n
+
1
. Let us set C
s
=
s
(
s
+
1
)
. Show that the product
(
C
m
+
1
−
C
k
)(
C
m
+
2
−
C
k
)
· · ·
(
C
m
+
n
−
C
k
)
is divisible by C
1
C
2
· · ·
C
n
.
(18th International Mathematical Olympiad)
Solution.
We use the identity
C
p
−
C
q
=
p
(
p
+
1
)
−
q
(
q
+
1
)
=
(
p
−
q
)(
p
+
q
+
1
),
which is valid for all positive integers
p
and
q
. Then one has
C
m
+
i
−
C
k
=
(
m
−
k
+
i
)(
m
+
k
+
i
+
1
),
for all
i
=
1
,
2
, . . . ,
n
.
For the given products we obtain respectively the formulas
(
C
m
+
1
−
C
k
)
· · ·
(
C
m
+
n
−
C
k
)
=
n
i
=
1
(
m
−
k
+
i
)
n
i
=
1
(
m
+
k
+
1
+
i
),
C
1
C
2
· · ·
C
n
=
n
!
(
n
+
1
)
!
.
Their quotient is the product of two rational fractions:
n
i
=
1
(
m
−
k
+
i
)
n
!
and
n
i
=
1
(
m
+
k
+
1
+
i
)
(
n
+
1
)
!
.
It is known that the product of any
n
consecutive integers is divisible by
n
!
and their quotient is zero or a binomial coefficient, possibly multiplied by
−
1. In
our case we have
1
n
!
n
i
=
1
(
m
−
k
+
i
)
=
m
−
k
+
n
n
.

---

10.1. Binomial Coefficients
357
For the second fraction, a factor is missing in the numerator. We support our
argument by using the fact that
m
+
k
+
1 is a prime number greater than
n
+
1:
1
(
n
+
1
)
!
n
i
=
1
(
m
+
k
+
1
+
i
)
=
1
m
+
k
+
1
·
1
(
n
+
1
)
!
n
i
=
0
(
m
+
k
+
1
+
i
)
=
1
m
+
k
+
1
m
+
k
+
n
+
1
n
+
1
.
Note that
1
m
+
k
+
1
m
+
k
+
n
+
1
n
+
1
=
1
n
+
1
m
+
k
+
n
+
1
n
.
Since the first expression has denominator 1 or the prime
m
+
k
+
1 and the
second expression has denominator at most
n
+
1
<
m
+
k
+
1, both must be
integers.
Hence the binomial coefficient
m
+
k
+
n
+
1
n
+
1
is an integer that is divisible by
m
+
k
+
1, so our number is integer.
Problem 10.1.10.
Let n
,
k be arbitrary positive integers. Show that there exist
positive integers a
1
>
a
2
>
a
3
>
a
4
>
a
5
>
k such that
n
= ±
a
1
3
±
a
2
3
±
a
3
3
±
a
4
3
±
a
5
3
.
(2000 Romanian International Mathematical Olympiad Team Selection Test)
Solution.
For fixed
k
, choose
m
>
k
such that
n
+
m
3
is an odd number. We see
that this is possible by considering the parity of
n
. If
n
is an odd number, take
m
≡
0
(
mod 4
)
, and if
n
is an even number, take
m
≡
3
(
mod 4
)
.
Since
n
+
m
3
is an odd number, we express it in the form
n
+
m
3
=
2
a
+
1
.
Then use the identity
2
a
+
1
=
a
3
−
a
+
1
3
−
a
+
2
3
+
a
+
3
3
to obtain
n
=
a
3
−
a
+
1
3
−
a
+
2
3
+
a
+
3
3
−
m
3
.

---

358
II Solutions, 10. Problems Involving Binomial Coefficients
Notice that for
m
≥
3 we may ensure that
a
=
n
−
1
+
m
3
2
>
m
,
yielding the desired representation.
Problem 10.1.11.
Prove that if n and m are integers, and m is odd, then
1
3
m
n
m
k
=
0
3
m
3
k
(
3
n
−
1
)
k
is an integer.
(2004 Romanian International Mathematical Olympiad Team Selection Test)
Solution.
Let
ω
=
e
2
π
i
3
. Then
3
m
k
=
0
3
m
3
k
(
3
n
−
1
)
k
=
(
1
+
3
√
3
n
−
1
)
3
m
+
(
1
+
ω
3
√
3
n
−
1
)
3
m
+
(
1
+
ω
2
3
√
3
n
−
1
)
3
m
.
(1)
The right side of the above equality is the sum of the 3
m
th powers of the roots
x
1
,
x
2
,
x
3
of the polynomial
(
X
−
1
)
3
−
(
3
n
−
1
)
=
X
3
−
3
X
2
+
3
X
−
3
n
.
Let
s
k
=
x
k
1
+
x
k
2
+
x
k
3
. Then
s
0
=
s
1
=
s
2
=
3 and
s
k
+
3
=
3
s
k
+
2
−
3
s
k
+
1
+
3
ns
k
.
(
2
)
It follows by induction that each
s
k
is an integer divisible by 3
k
/
3
+
1
. A re-
peated application of (2) yields
s
k
+
7
=
63
ns
k
+
2
−
9
(
n
2
−
3
n
−
3
)
s
k
+
1
+
27
n
(
2
n
+
1
)
s
k
.
Since
s
3
=
9
n
, it follows inductively that
s
6
k
+
3
is divisible by 3
2
k
+
2
n
for all
nonnegative integers
k
, and the conclusion follows by (1).
Problem 10.1.12.
Show that for every positive integer n the number
n
k
=
0
2
n
+
1
2
k
+
1
2
3
k
is not divisible by
5
.
(16th International Mathematical Olympiad)

---

10.1. Binomial Coefficients
359
Solution.
Let us consider the binomial formula:
(
1
+
2
√
2
)
2
n
+
1
=
(
1
+
2
3
2
)
2
n
+
1
=
2
n
+
1
i
=
0
2
n
+
1
i
2
3
i
2
=
n
i
=
0
2
n
+
1
2
i
2
3
i
+
n
i
=
0
2
n
+
1
2
i
+
1
2
3
i
·
2
3
2
=
a
n
+
b
n
√
8
,
where
a
n
=
n
i
=
0
2
n
+
1
2
i
2
3
i
and
b
n
=
n
i
=
0
2
n
+
1
2
i
+
1
2
3
i
.
In a similar way,
(
1
−
2
√
2
)
2
n
+
1
=
a
n
−
b
n
√
8
.
After multiplying these two equalities, we obtain
−
7
2
n
+
1
=
a
2
n
−
8
b
2
n
. If
b
n
≡
0
(
mod 5
)
, the above equality gives
a
2
n
≡ −
2
(
mod 5
)
≡
3
(
mod 5
)
.
Since 3 is not a perfect square modulo 5, we obtain a contradiction.
Problem 10.1.13.
Prove that for a positive integer k there is an integer n
≥
2
such that
n
1
, . . . ,
n
n
−
1
are all divisible by k if and only if k is a prime.
Solution.
If
k
is a prime we take
n
=
k
, and the property holds (see property 7 in