Show that $\frac{(m+n-1)!}{m!n!}$ is an integer where m and n are positive integers and gcd(m,n)=1 I need to prove that $\frac{(m+n-1)!}{m!n!}$ is an integer there is a question here which is similar to this question but i cant figure out how I can insert the '-1' in there. Thanks
 A: Hint: This is equivalent to showing that $m+n$ divides $\binom{m+n}{m}$, or equivalently $a$ divides $\binom{a}{b}$ for any $a>b$ where $\gcd(a,b)=1$. See if you can partition the subsets of $a$ objects with $b$ elements into blocks of $a$ to prove this combinatorially. If you know it, you might want to recall the "necklace proof" of Fermat's Little Theorem - this has a similar flavor.
A: Since 
$$\frac{(m+n-1)!}{m!n!}=\frac{(m+n)}{(m+n)}\frac{(m+n-1)!}{m!n!}=\frac{1}{m+n}\binom{m+n}{m}.$$
So we need to show that $\frac{1}{m+n}\binom{m+n}{m}$ is an integer. Observe that $\gcd(m,n)=1$ also implies that $\color{blue}{\gcd(m+n,m)=1}$. Since $\gcd(a,b)$ is a linear combination of $a$ and $b$. Therefore,
\begin{align*}
\frac{1}{m+n}\binom{m+n}{m} &=\frac{\color{blue}{\gcd(m+n,m)}}{m+n}\binom{m+n}{m}\\
&=\frac{\color{blue}{x(m+n)+y(m)}}{m+n}\binom{m+n}{m} &\text{for some } x,y \in \Bbb{Z}\\
&=x\left[\color{green}{\frac{m+n}{m+n}\binom{m+n}{m}}\right]+y\left[\color{red}{\frac{m}{m+n}\binom{m+n}{m}}\right].
\end{align*}
The quantity $\color{green}{\frac{m+n}{m+n}\binom{m+n}{m}}=\binom{m+n}{m}$ is definitely an integer and the quantity
$$\color{red}{\frac{m}{m+n}\binom{m+n}{m}}=\binom{m+n-1}{m-1}$$
is also an integer.
This implies  that $\frac{1}{m+n}\binom{m+n}{m}$ is an integer combination of these two integers, hence an integer itself.
