MathDB
Problems
Contests
National and Regional Contests
PEN Problems
PEN A Problems
70
A 70
A 70
Source:
May 25, 2007
induction
binomial coefficients
Divisibility Theory
Problem Statement
Suppose that
m
=
n
q
m=nq
m
=
n
q
, where
n
n
n
and
q
q
q
are positive integers. Prove that the sum of binomial coefficients
∑
k
=
0
n
−
1
(
gcd
(
n
,
k
)
q
gcd
(
n
,
k
)
)
\sum_{k=0}^{n-1}{ \gcd(n, k)q \choose \gcd(n, k)}
k
=
0
∑
n
−
1
(
g
cd
(
n
,
k
)
g
cd
(
n
,
k
)
q
)
is divisible by
m
m
m
.
Back to Problems
View on AoPS