Suppose that $S=\{a_{1}, \cdots, a_{r}\}$ is a set of positive integers, and let $S_{k}$ denote the set of subsets of $S$ with $k$ elements. Show that \[\text{lcm}(a_{1}, \cdots, a_{r})=\prod_{i=1}^{r}\prod_{s\in S_{i}}\gcd(s)^{\left((-1)^{i}\right)}.\]
Problem
Source:
Tags: number theory, least common multiple, greatest common divisor, Divisibility Theory
14.09.2007 23:03
To prove equality, we will look at the exponent of any prime $ p$. If this is equal for any $ p$, both sides are equal. Terms $ a_{i}$ that do not divide $ p$ clearly don't affect this on both sides. So we can assume either only terms divisible by $ p$, or no terms divisible by $ p$. Since $ \sum_{i=1}^{r}(-1)^{i}\binom{r}{i}=1$, cancelling a factor $ p$ from all $ a_{i}$ leaves the equality invariant. So we can assume that no terms divide $ p$. But then there stands $ 1=1$ for the exponent of $ p$, so we're done.
04.07.2010 09:17
Peter wrote: Suppose that $S=\{a_{1}, \cdots, a_{r}\}$ is a set of positive integers, and let $S_{k}$ denote the set of subsets of $S$ with $k$ elements. Show that \[\text{lcm}(a_{1}, \cdots, a_{r})=\prod_{i=1}^{r}\prod_{s\in S_{i}}\gcd(s)^{\left((-1)^{i}\right)}.\] ler r=2,then $[a_1,a_2]=(a_1,a_2)(a_1a_2)^{-1}$. That's wrong! I think there is an error.
04.07.2010 12:50
The formula should be $\mathrm{lcm}(a_1,..., a_r)=\prod_{i=1}^r\prod_{s\in S_i}\mathrm{gcd}(s)^{(-1)^{i+1}}$.
27.07.2016 16:22
Peter wrote: $ \sum_{i=1}^{r}(-1)^{i}\binom{r}{i}=1$ I don't think this is true? For example, when $r=6$ yields that this quantity is $-1$. Does anyone have a correct solution to this?