Prove that $\gcd{\left(\binom M1,\binom M2,\binom M3,\ldots,\binom Mn\right)}=1$ where $M=\mathrm{lcm}(1,2,3,\ldots,n)$ Let $n$ be a positive integer and let
$$M=\mathrm{lcm}(1,2,3,\ldots,n).$$
Show that
$$\gcd{\left(\binom{M}{1},\binom{M}{2},\binom{M}{3},\ldots,\binom{M}{n}\right)}=1$$
 A: HINT: Suppose that $p$ is a prime dividing $M$, and that $p^k$ is the highest power of $p$ dividing $M$.


*

*Show that $p^k\le n$.  

*Show that if $M=ap^k$, and $1\le t\le p^k$, then $(a-1)p^k+t$ is divisible by the same maximum power of $p$ as $t$.  

*Conclude that $p$ does not divide $\dbinom{M}{p^k}$.

A: Hint: Apply Lucas' Theorem which states that for non-negative integers $m$ and $n$, and a prime $p$, $$ {m \choose n} \equiv \prod_{i=0}^{k} {m_{i} \choose n_{i}} \pmod p,$$ where $m=m_{k}p^{k}+m_{k-1}p^{k-1}+\cdots+m_{1}p+m_{0}$ and $n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots+n_{1}p+n_{0}$ are the base $p$ expansions of $m$ and $n,$ respectively.  This uses the convention that ${m \choose n} =0$ when $m<n$ and ${0\choose 0 } = 1$.

Corollary: For any $M$, if $n \geq p^k$ for every prime $p$ such that $M = p^k q$ where $q \not\mid p$, then
$$\gcd{\left(\binom{M}{1},\binom{M}{2},\binom{M}{3},\ldots,\binom{M}{n}\right)}=1$$
Proof: Fix prime $p$, let $M=p^k q$ where $ q\not \mid p$. Then from Lucas' Theorem, ${M \choose p^k} \neq 0 \pmod{p}$. (In fact, it is equal to $q \pmod{p}$.)
Hence, the gcd is not divisible by any prime, so must be equal to 1.

The condition in the corollary is clearly satisfied when $M=\mathrm{lcm}(1,2,3,\ldots,n).$
A: For a prime $p$ and a positive integer $r$, let $v_p(r)$ denote the largest positive integer $k$ such that $p^k \mid r$. Note that $v_p(r_1r_2) = v_p(r_1)+v_p(r_2)$ for any positive integers $r_1,r_2$, and $v_p(\frac{r_1}{r_2}) = v_p(r_1)-v_p(r_2)$ for any positive integers $r_1,r_2$ with $r_2 \mid r_1$. Also note that if $v_p(r) = k$, then, for any $1 \le j \le p^k$, $v_p(r+p^k+j) = v_p(j)$. 
Main Problem: Suppose for the sake of contradiction that there is some prime $p$ dividing $M$. Let $k = v_p(M)$. Then, $v_p({M \choose p^k}) = v_p(\frac{M(M-1)\dots(M-p^k+1)}{(p^k)!}) = v_p(\prod_{j=1}^{p^k} (M-p^k+j))-v_p(\prod_{j=1}^{p^k} j) = \sum_{j=1}^{p^k} v_p(j)-\sum_{j=1}^{p^k} v_p(j) = 0$. This shows $p$ does not divide ${M \choose p^k}$. Finally, since $p^k \mid M = lcm(1,2,\dots,n)$, we have $p^k \le n$. 
