シンプルながらも教育的な問題です。
正整数$a$、$b$の最大公約数を$(a,b)$で表す。
（１）任意の正整数$m$、$n$に対して、等式$$(m+n,n)=(m, n)$$が成り立つことを証明せよ。
（２）互いに素な正整数$m$、$n$に対して、$(m+n-1)!$ は $m!n!$ によって割り切れることを証明せよ。
（2021年奈良県立医科大学 後期第3問）
考え方
（１）はユークリッドの互除法を用いれば明らかなように思われますが、ここでは最大公約数を文字で置いて証明します。（２）は二項係数との関連に気が付けるかがポイントです。（１）で与えられたヒントを上手く使いましょう。
解答例
（１）
$(m+n, n)=d_{1}$、$(m, n)=d_{2}$ と置く。
このとき、整数$k_{1}$、$l_{1}$を用いて $m+n=k_{1} d_{1}$、$n=l_{1} d_{1}$ と書けて、$$m=\left(k_{1}-l_{1}\right) d_{1}, \quad n=l_{1} d_{1}$$と表せる。これより$d_{1}$は正整数$m$と$n$の公約数であるから、$$d_{1} \leqq (m,n)=d_2 \quad \cdots ①$$を得る。
また、整数$k_{2}$、$l_{2}$を用いて $m=k_{2} d_{2}$、$n=l_{2} d_{2}$ と書けて、$$m+n=\left(k_{2}+l_{2}\right) d_{2}, \quad n=l_{2} d_{2}$$と表せる。これより$d_{2}$は正整数 $m+n$ と$n$の公約数であるから、$$d_{2} \leqq (m+n,n)=d_1 \quad \cdots ②$$を得る。
以上、$①$と$②$より $d_{1} \leqq d_2$ かつ $d_{2} \leqq d_1$ となるから、$d_1=d_2$ である。よって示された。
□
（２）
$$\begin{aligned}{ }_{m+n} \mathrm{C}_{n} &=\dfrac{(m+n)!}{m!n!} \\ &=\dfrac{m+n}{n} \cdot \dfrac{(m+n-1) !}{m!(n-1)!} \\ &=\dfrac{m+n}{n} \cdot{ }_{m+n-1} \mathrm{C}_{n-1} \end{aligned}$$より、$$n \cdot{ }_{m+n} \mathrm{C}_{n}=(m+n) \cdot {}_{m+n-1} \mathrm{C}_{m-1}$$を得る。ここで（１）より $(m+n,n)=(m, n)$ が成り立つから、${ }_{m+n} \mathrm{C}_{n}$ が $m+n$ の倍数であることが従う。
よって $\dfrac{{ }_{m+n} \mathrm{C}_{n}}{m+n}$、つまり $\dfrac{(m+n-1)!}{m!n!}$ は整数であるから、$(m+n-1)!$ は $m!n!$ によって割り切れることが示された。
□
本問は後期試験の問題ですが、整数分野の基礎的な知識の積み重ねで解答できます。奈良医大が公開している「出題の意図」には次のようにあります。
本問は階乗!を用いて表示された正整数の整除について問う問題である。前半(1)は初等整数論の基本であるユークリッド互除法の原理の確認、後半(2)は二項係数と(1)とを組み合わせることで、結論を導出する発想力・論証能力等の総合力を問う。
（１）は互除法の原理を用いて丁寧に証明すると解答例のようになります。$d_1=d_2$ の成立を示すために $d_{1} \leqq d_2$ かつ $d_{2} \leqq d_1$ を示すという方法は最大公約数の議論などでしばしば見かけます。
（２）で${ }_{m+n} \mathrm{C}_{n}$を連想する点が本問の難所でしょうか。これは、「$\dfrac{(m+n-1)!}{m!n!}$ という分数が整数であること」を（１）のヒントを使っていかに示すか、を考えることで思い至るはずです。これも結局は「積の形に変形して約数（倍数）の候補を絞り込む」という整数問題の基本解法を利用しているに過ぎません。積の形を作ってあげれば、（１）の結論と「互いに素」という仮定が上手くハマります。