MathDB
Problems
Contests
National and Regional Contests
PEN Problems
PEN A Problems
68
68
Part of
PEN A Problems
Problems
(1)
A 68
Source:
5/25/2007
Suppose that
S
=
{
a
1
,
⋯
,
a
r
}
S=\{a_{1}, \cdots, a_{r}\}
S
=
{
a
1
,
⋯
,
a
r
}
is a set of positive integers, and let
S
k
S_{k}
S
k
denote the set of subsets of
S
S
S
with
k
k
k
elements. Show that
lcm
(
a
1
,
⋯
,
a
r
)
=
∏
i
=
1
r
∏
s
∈
S
i
gcd
(
s
)
(
(
−
1
)
i
)
.
\text{lcm}(a_{1}, \cdots, a_{r})=\prod_{i=1}^{r}\prod_{s\in S_{i}}\gcd(s)^{\left((-1)^{i}\right)}.
lcm
(
a
1
,
⋯
,
a
r
)
=
i
=
1
∏
r
s
∈
S
i
∏
g
cd
(
s
)
(
(
−
1
)
i
)
.
number theory
least common multiple
greatest common divisor
Divisibility Theory