|
10.1. Binomial Coefficients
201
First solution.
We first show uniqueness. Suppose
m
is represented by two se-
quences
a
k
, . . . ,
a
t
and
b
k
, . . . ,
b
t
. Find the first position in which they differ;
without loss of generality, assume that this position is
k
and that
a
k
>
b
k
. Then
m
≤
b
k
k
+
b
k
−
1
k
−
1
+ · · · +
b
k
−
k
+
1
1
<
b
k
+
1
k
≤
m
,
a contradiction.
To show existence, apply the greedy algorithm: find the largest
a
k
such that
a
k
k
≤
m
, and apply the same algorithm with
m
and
k
replaced by
m
−
a
k
k
and
k
−
1. We need only make sure that the sequence obtained is indeed decreasing,
but this follows because by assumption,
m
<
a
k
+
1
m
, and so
m
−
a
k
k
<
a
k
k
−
1
.
Second solution.
Sort all unordered
k
-tuples of distinct nonnegative integers lex-
icographically. Then the
k
-tuple
{
a
k
,
a
k
−
1
, . . . ,
a
t
,
t
−
1
,
t
−
3
, . . . ,
0
}
is preceded
by exactly
a
k
k
+
a
k
−
1
k
−
1
+ · · · +
a
t
t
other
k
-tuples. (The first term counts the
number of
k
-tuples whose largest element is smaller than
a
k
. The second term
counts
k
-tuples that begin with
a
k
but whose second-largest element is smaller
than
a
k
−
1
, etc.) Since there is necessarily a unique
k
-tuple preceded by
m
other
k
-tuples, every
m
has a unique representation in this form.
Problem 10.1.6.
Show that for every positive integer n
≥
3
, the least common
multiple of the numbers
1
,
2
, . . . ,
n is greater than
2
n
−
1
.
(1999 Czech–Slovak Match)
Solution.
For any
n
≥
3 we have
2
n
−
1
=
n
−
1
k
=
0
n
−
1
k
<
n
−
1
k
=
0
n
−
1
n
−
1
2
=
n
n
−
1
n
−
1
2
.
Hence it suffices to show that
n
n
−
1
n
−
1
2
divides lcm
(
1
,
2
, . . . ,
n
)
. Using an
argument involving prime factorizations, we will prove the more general assertion
that for each
k
<
n
, lcm
(
n
,
n
−
1
, . . . ,
n
−
k
)
is divisible by
n
n
−
1
k
.
Let
k
and
n
be fixed natural numbers with
k
<
n
, and let
p
≤
n
be an arbitrary
prime. Let
p
α
be the highest power of
p
that divides lcm
(
n
,
n
−
1
, . . . ,
n
−
k
)
,
where
p
α
|
n
−
l
for some
l
. Then for each
i
≤
α
, we know that
p
i
|
n
−
l
. Thus
exactly
l
p
i
of
{
n
−
l
+
1
,
n
−
l
+
2
, . . . ,
n
}
and exactly
k
−
l
p
i
of
{
n
−
l
−
1
,
n
−
l
−
2
, . . . ,
n
−
k
}
are multiples of
p
i
, so
p
i
divides
l
p
i
+
k
−
l
p
i
≤
k
p
i
of the
remaining
k
numbers, that is, at most the number of multiples of
p
i
between 1
and
k
. It follows that
p
divides
n
n
−
1
k
=
n
(
n
−
1
)
· · ·
(
n
−
l
+
1
)(
n
−
l
−
1
)
· · ·
(
n
−
k
)
k
!
(
n
−
l
)
at most
α
times, so that indeed
n
n
−
1
k
|
lcm
(
n
,
n
−
1
, . . . ,
n
−
k
)
.
202
I Fundamentals, 10. Problems Involving Binomial Coefficients
Additional Problems
Problem 10.1.7.
Show that the sequence
2002
2002
,
2003
2002
,
2004
2002
, . . . ,
considered modulo 2002, is periodic.
(2002 Baltic Mathematical Competition)
Problem 10.1.8.
Prove that
2
p
p
≡
2
(
mod
p
2
)
for any prime number
p
.
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)
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)
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)
Problem 10.1.12.
Show that for any 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)
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.
10.2. Lucas’s and Kummer’s Theorems
203
10.2
Lucas’s and Kummer’s Theorems
The following theorems of E. Lucas
2
(1878) and E. Kummer
3
(1852) are very
useful in number theory. Let
n
be a positive integer, and let
p
be a prime. Let
n
m
n
m
−
1
· · ·
n
0
p
denote the base-
p
representation of
n
; that is,
n
=
n
m
n
m
−
1
· · ·
n
0
p
=
n
0
+
n
1
p
+ · · · +
n
m
p
m
,
where 0
≤
n
0
,
n
1
, . . . ,
n
m
≤
p
−
1 and
n
m
=
0.
Theorem 10.2.1.
(Lucas)
Let p be a prime, and let n be a positive integer with n
=
n
m
n
m
−
1
· · ·
n
0
p
. Let i be a positive integer less than n. If i
=
i
0
+
i
1
p
+· · ·+
i
m
p
m
,
where
0
≤
i
0
,
i
1
, . . . ,
i
m
≤
p
−
1
, then
n
i
≡
m
j
=
0
n
j
i
j
(
mod
p
).
(
1
)
Here
0
0
=
1
and
n
j
i
j
=
0
if n
j
<
i
j
.
To prove this theorem, we need some additional techniques. Let
p
be a prime,
and let
f
(
x
)
and
g
(
x
)
be two polynomials with integer coefficients. We say that
f
(
x
)
is congruent to
g
(
x
)
modulo
p
, and write
f
(
x
)
≡
g
(
x
) (
mod
p
)
, if all of
the coefficients of
f
(
x
)
−
g
(
x
)
are divisible by
p
. (Note that the congruence of
polynomials is different from the congruence of the values of polynomials. For
example,
x
(
x
+
1
)
≡
0
(
mod 2
)
even though
x
(
x
+
1
)
is divisible by 2 for all
integers
x
.) The following properties can be easily verified:
(a)
f
(
x
)
≡
f
(
x
) (
mod
p
)
;
(b) if
f
(
x
)
≡
g
(
x
) (
mod
p
)
, then
g
(
x
)
≡
f
(
x
) (
mod
p
)
;
(c) if
f
(
x
)
≡
g
(
x
) (
mod
p
)
and
g
(
x
)
≡
h
(
x
) (
mod
p
)
, then
f
(
x
)
≡
h
(
x
) (
mod
p
)
;
(d) if
f
(
x
)
≡
g
(
x
) (
mod
p
)
and
f
1
(
x
)
≡
g
1
(
x
) (
mod
p
)
, then
f
(
x
)
±
f
1
(
x
)
≡
g
(
x
)
±
g
1
(
x
) (
mod
p
)
and
f
(
x
)
f
1
(
x
)
≡
g
(
x
)
g
1
(
x
) (
mod
p
).
Do'stlaringiz bilan baham: |
